摘要：轉(zhuǎn)載史上最簡(jiǎn)單的平衡樹(shù)無(wú)旋作者博客地址使用此文件時(shí)請(qǐng)保留上述信息謝謝合作覺(jué)得文章不錯(cuò)請(qǐng)點(diǎn)擊鏈接為博客點(diǎn)贊高能預(yù)警所有示例代碼都是數(shù)組版的歡迎前置知識(shí)線段樹(shù)請(qǐng)確保你完全理解最基礎(chǔ)的線段樹(shù)和區(qū)間加法和區(qū)間求和一簡(jiǎn)介無(wú)旋又稱(chēng)是范浩強(qiáng)大佬發(fā)明的一種

前置知識(shí):線段樹(shù)!請(qǐng)確保你完全理解最基礎(chǔ)的線段樹(shù)和LazyTag(區(qū)間加法和區(qū)間求和).

無(wú)旋Treap,又稱(chēng)fhq_treap,是范浩強(qiáng)大佬發(fā)明的一種強(qiáng)力數(shù)據(jù)結(jié)構(gòu).

總的來(lái)說(shuō),它可以支持一切Treap和Splay等平衡樹(shù)的操作,支持可持久化(但是這篇博客不會(huì)講),常數(shù)遠(yuǎn)小于Splay,但是處理LCT問(wèn)題略比Splay遜色,以至于我到現(xiàn)在還不會(huì).

對(duì)于初學(xué)者來(lái)說(shuō),它比Splay好學(xué),比Treap好用,實(shí)在不失為一個(gè)性價(jià)比極高的數(shù)據(jù)結(jié)構(gòu).

首先讓我們來(lái)復(fù)習(xí)一下平衡樹(shù)們的祖宗——二叉搜索樹(shù)的性質(zhì):

遞歸定義,空樹(shù)是一棵二叉搜索樹(shù),二叉搜索樹(shù)的左子樹(shù)的最大點(diǎn)權(quán)小等于根的點(diǎn)權(quán)小等于右子樹(shù)的最小點(diǎn)權(quán),二叉搜索樹(shù)的左右子樹(shù)也是二叉搜索樹(shù).

二叉搜索樹(shù)的插入,刪除,搜索等操作都容易被極端數(shù)據(jù)卡滿復(fù)雜度,這時(shí)我們就需要各種神奇操作來(lái)確保它的樹(shù)高期望大小為log級(jí)別.我們直接看無(wú)旋Treap是如何操作的(因?yàn)槠渌麕追N我不大會(huì)):

無(wú)旋Treap有兩種基本操作:

將樹(shù)分為兩棵樹(shù),其中樹(shù)A的最大點(diǎn)權(quán)小等于樹(shù)B的最小點(diǎn)權(quán).因?yàn)闃?shù)高期望為log,所以單次操作的復(fù)雜度期望為log.

將兩棵樹(shù)合為一棵樹(shù),其中樹(shù)A的最大點(diǎn)權(quán)小等于樹(shù)B的最小點(diǎn)權(quán).為了保證樹(shù)高期望為log,我們要想辦法隨機(jī)合并.

沒(méi)了(臥槽你啥都沒(méi)說(shuō)啊).

好吧,為了博客過(guò)審,還是再來(lái)仔細(xì)講一下.

以下實(shí)例代碼中,0代表空節(jié)點(diǎn),Pushdown代表下傳標(biāo)記,Pushup代表向上更新.

先來(lái)看一眼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為當(dāng)前準(zhǔn)備拆開(kāi)的節(jié)點(diǎn),A和B為左右子樹(shù)根節(jié)點(diǎn)的指針,Siz為拆分出的左子樹(shù)的大小.

翻譯成人話:當(dāng)拆分的大小不超過(guò)左子樹(shù)大小時(shí),當(dāng)前節(jié)點(diǎn)會(huì)被分配到右子樹(shù)(B=Nod),然后進(jìn)入左子樹(shù)進(jìn)行拆分,拆分下來(lái)的左子樹(shù)仍舊傳到A,拆下來(lái)的右子樹(shù)則作為當(dāng)前節(jié)點(diǎn)的左子樹(shù),否則同理.

首先確保你對(duì)指針有初步的認(rèn)識(shí)(因?yàn)槲乙仓挥谐醪降恼J(rèn)識(shí)),然后確保你牢記了二叉搜索樹(shù)的性質(zhì)(這樣你才能理解為什么要這樣拆分,不論如何拆分都不能改變節(jié)點(diǎn)從小到大中序排序的定律).

如果是按照權(quán)值拆分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是隨機(jī)權(quán)值,這樣我們就可以保證樹(shù)高的期望為log(蒟蒻口胡:因?yàn)樾纬砷L(zhǎng)度為n的鏈的概率大概為$frac{1}{2^n}$乘一個(gè)組合數(shù)什么的).

兩種合并方法是等價(jià)的.都是把其中一個(gè)節(jié)點(diǎn)當(dāng)作這一步的根節(jié)點(diǎn),另一個(gè)節(jié)點(diǎn)和根節(jié)點(diǎn)的子樹(shù)遞歸合并.請(qǐng)?jiān)俅位貞浂嫠阉鳂?shù)的性質(zhì),所以我們一定要保證A在B的"左邊".

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

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

查排名,查前驅(qū)后繼等操作同普通平衡樹(shù),在樹(shù)上dfs即可.不過(guò)為了體現(xiàn)無(wú)旋Treap的優(yōu)越,下方給出的實(shí)例代碼是利用兩種基本操作實(shí)現(xiàn)的,優(yōu)點(diǎn)在于直觀,好寫(xiě),缺點(diǎn)在于比起直接dfs的話常數(shù)略大.

新建一個(gè)節(jié)點(diǎn),然后根據(jù)權(quán)值拆成左右子樹(shù),然后Merge(Merge(左,新節(jié)點(diǎn)),右)即可.

根據(jù)權(quán)值拆成左右子樹(shù)和要拆除的節(jié)點(diǎn),然后直接Merge(左,右)即可.

一般來(lái)講是通過(guò)Split剖出你需要操作的區(qū)間代表的子樹(shù),然后在根節(jié)點(diǎn)打標(biāo)記,然后合并即可.

需要支持插入,刪除,查元素排名和排名元素,查前驅(qū)后繼.

模板題,把上面除了區(qū)間操作以外的東西實(shí)現(xiàn)好即可.

AC代碼:https://www.luogu.org/recordn...
開(kāi)啟O2優(yōu)化,洛谷更新數(shù)據(jù)后262ms

一個(gè)1到N的排列,M次操作,每次翻轉(zhuǎn)一個(gè)區(qū)間,求最后的排列.

只用實(shí)現(xiàn)區(qū)間操作即可,具體如何打標(biāo)記,下傳標(biāo)記請(qǐng)看代碼.

AC代碼:https://www.luogu.org/recordn...
開(kāi)啟O2優(yōu)化,洛谷更新數(shù)據(jù)后488ms

區(qū)間加,區(qū)間求和.

這個(gè)例子是為了方便大家理解LazyTag,做好線段樹(shù)到平衡樹(shù),或者普通平衡樹(shù)到區(qū)間平衡樹(shù)的銜接,特意忍辱負(fù)重寫(xiě)了這篇代碼.是不是超級(jí)良心~

AC代碼:https://www.luogu.org/recordn...
開(kāi)啟O2優(yōu)化,洛谷更新數(shù)據(jù)后642ms

為什么最水的一題代碼反而最慢啊,新數(shù)據(jù)也太強(qiáng)了吧.

什么?博客太爛了看不懂?

推薦閱讀:http://iwo.im/?q=%E6%97%A0%E6...

(↑↑↑看完你會(huì)回來(lái)點(diǎn)贊的.)

本文PDF文件:

鏈接：https://pan.baidu.com/s/1vR9d...

提取碼：mnc4

僅供學(xué)習(xí)交流使用!!!謝謝配合!!!