作者：fzszkl

鏈接：ac.nowcoder.com/discuss

來源：牛客網

使用此PDF文件時請保留上述信息！謝謝合作！覺得文章不錯請點擊鏈接為博客點贊！

高能預警：所有示例代碼都是數組版的,歡迎copy！

前置知識：線段樹！請確保你完全理解最基礎的線段樹和LazyTag（區間加法和區間求和）。

一、簡介

無旋Treap,又稱fhq_treap,是范浩強大佬發明的一種強力數據結構.

總的來說,它可以支持一切Treap和Splay等平衡樹的操作,支持可持久化(但是這篇博客不會講),常數遠小於Splay,但是處理LCT問題略比Splay遜色,以至於我到現在還不會.

對於初學者來說,它比Splay好學,比Treap好用,實在不失為一個性價比極高的數據結構.

二、詳解

首先讓我們來複習一下平衡樹們的祖宗——二叉搜索樹的性質:

遞歸定義,空樹是一棵二叉搜索樹,二叉搜索樹的左子樹的最大點權小等於根的點權小等於右子樹的最小點權,二叉搜索樹的左右子樹也是二叉搜索樹.

二叉搜索樹的插入,刪除,搜索等操作都容易被極端數據卡滿複雜度,這時我們就需要各種神奇操作來確保它的樹高期望大小為log級別.我們直接看無旋Treap是如何操作的(因為其他幾種我不大會):

無旋Treap有兩種基本操作:

(1)分裂Split

將樹分為兩棵樹,其中樹A的最大點權小等於樹B的最小點權.因為樹高期望為log,所以單次操作的複雜度期望為log.

(2)合併Merge

將兩棵樹合為一棵樹,其中樹A的最大點權小等於樹B的最小點權.為了保證樹高期望為log,我們要想辦法隨機合併.

沒了(卧槽你啥都沒說啊).

好吧,為了博客過審,還是再來仔細講一下.

以下實例代碼中,0代表空節點,Pushdown代表下傳標記,Pushup代表向上更新.

先來看一眼Split:

void Split( int Nod , int Siz , int &A , int &B ) {
if( Nod == 0 ) return (void)( A = B = 0 ) ;
Pushdown( Nod ) ;
if( Siz <= Size[Ls[Nod]] ) B = Nod , Split( Ls[Nod] , Siz , A , Ls[Nod] ) ;
else A = Nod , Split( Rs[Nod] , Siz - Size[Ls[Nod]] - 1 , Rs[Nod] , B ) ;
Pushup( Nod ) ;
}

Nod為當前準備拆開的節點,A和B為左右子樹根節點的指針,Siz為拆分出的左子樹的大小.

翻譯成人話:當拆分的大小不超過左子樹大小時,當前節點會被分配到右子樹(B=Nod),然後進入左子樹進行拆分,拆分下來的左子樹仍舊傳到A,拆下來的右子樹則作為當前節點的左子樹,否則同理.

首先確保你對指針有初步的認識(因為我也只有初步的認識),然後確保你牢記了二叉搜索樹的性質(這樣你才能理解為什麼要這樣拆分,不論如何拆分都不能改變節點從小到大中序排序的定律).

如果是按照權值拆分Split,稍微改一下就好了.

然後看一眼Merge:

int Merge( int A , int B ) {
if( A == 0 or B == 0 ) return A | B ;
register int Ans ;
Pushdown( A ) ;
Pushdown( B ) ;
if( Pos[A] > Pos[B] ) Rs[A] = Merge( Rs[A] , B ) , Ans = A ;
else Ls[B] = Merge( A , Ls[B] ) , Ans = B ;
Pushup( Ans ) ;
return Ans ;
}

Pos是隨機權值,這樣我們就可以保證樹高的期望為log(蒟蒻口胡:因為形成長度為n的鏈的概率大概為 frac{1}{2^n} 乘一個組合數什麼的).

兩種合併方法是等價的.都是把其中一個節點當作這一步的根節點,另一個節點和根節點的子樹遞歸合併.請再次回憶二叉搜索樹的性質,所以我們一定要保證A在B的"左邊".

一定要注意啊,Merge(A,B)和Merge(B,A)天差地別啊!

有了這兩種看上去就特別nb的操作,我們組合一下,就可以完成很多nb的事情啦~

常規操作

查排名,查前驅後繼等操作同普通平衡樹,在樹上dfs即可.不過為了體現無旋Treap的優越,下方給出的實例代碼是利用兩種基本操作實現的,優點在於直觀,好寫,缺點在於比起直接dfs的話常數略大.

插入節點

新建一個節點,然後根據權值拆成左右子樹,然後Merge(Merge(左,新節點),右)即可.

刪除節點

根據權值拆成左右子樹和要拆除的節點,然後直接Merge(左,右)即可.

區間操作

一般來講是通過Split剖出你需要操作的區間代表的子樹,然後在根節點打標記,然後合併即可.

三、喜聞樂見小例題

(1)洛谷3369普通平衡樹:luogu.org/problemnew/sh

需要支持插入,刪除,查元素排名和排名元素,查前驅後繼.

模板題,把上面除了區間操作以外的東西實現好即可.

AC代碼:luogu.org/recordnew/sho

開啟O2優化,洛谷更新數據後262ms

(2)洛谷3391文藝平衡樹:luogu.org/problemnew/sh

一個1到N的排列,M次操作,每次翻轉一個區間,求最後的排列.

只用實現區間操作即可,具體如何打標記,下傳標記請看代碼.

AC代碼:luogu.org/recordnew/sho

開啟O2優化,洛谷更新數據後488ms

(3)洛谷3372線段樹:luogu.org/problemnew/sh

區間加,區間求和.

這個例子是為了方便大家理解LazyTag,做好線段樹到平衡樹,或者普通平衡樹到區間平衡樹的銜接,特意忍辱負重寫了這篇代碼.是不是超級良心~

AC代碼:luogu.org/recordnew/sho

開啟O2優化,洛谷更新數據後642ms

為什麼最水的一題代碼反而最慢啊,新數據也太強了吧.

四、售後保障

什麼？博客太爛了看不懂？

推薦閱讀：iwo.im/?

(↑↑↑看完你會回來點贊的.)

本文PDF文件：

鏈接：pan.baidu.com/s/1vR9daD

提取碼：mnc4

僅供學習交流使用!!!謝謝配合!!!

與作者交流：ac.nowcoder.com/discuss

更多演算法和題解：ac.nowcoder.com/acm/con


推薦閱讀：
相关文章