文章目錄

• 概念
• 全套模板
• • push_up模板
  • split拆樹模板(按權(quán)值拆)
  • split拆樹模板(按個(gè)數(shù)拆)
  • merge合并模板（地址版）
  • merge合并模板（帶返回根）
  • 區(qū)間模板
  • insert插入模板
  • delete刪除模板
  • find_kth找第k大模板
  • get_rank找排名模板
  • pre找前驅(qū)模板
  • suf找后驅(qū)模板
• 例題1：普通平衡樹
• • 題目
  • 代碼實(shí)現(xiàn)
• 例題2：文藝線段樹
• • 題目
  • 代碼實(shí)現(xiàn)

建議在看這篇博客之間要了解一下帶旋Treap
我會(huì)在模板前面寫上一部分的思路講解，幫助各位理解

概念

根據(jù)它的名字我們也可以得知，這種數(shù)據(jù)結(jié)構(gòu)就是$treap$的后代，只不過不帶旋轉(zhuǎn)，其余都是一致的
所以在運(yùn)用和代碼上會(huì)有所異同。它比$treap$多了$split$（拆樹）和$merge$（合并）操作，所以得到的結(jié)果是可以多處理數(shù)據(jù)結(jié)構(gòu)的區(qū)間問題。以一換一
接下來我們就重點(diǎn)介紹$split$和$merge$還有區(qū)間操作到底是個(gè)什么玩意兒？？？

全套模板

因?yàn)槭亲约盒薷暮蟮哪０?#xff0c;可能會(huì)有不嚴(yán)謹(jǐn)處，歡迎大家指出并更正！

先照樣介紹各個(gè)數(shù)組變量的含義：
$Size$：表示節(jié)點(diǎn)數(shù)量也可作最后一個(gè)點(diǎn)編號(hào)
$cnt[p]$：表示編號(hào)為$p$，值為$x$在$treap$中插入的次數(shù)
$key[p]$：表示該點(diǎn)$p$的值為$x$
$rd[p]$：就是我們自己搞的修正值，用$rand()$函數(shù)隨機(jī)生成
$siz[p]$：編號(hào)為$p$的子樹包括本身在內(nèi)的節(jié)點(diǎn)數(shù)量即大小
$son[p][2]$：$son[p][0]$表示p的左兒子，$son[p][1]$表示$p$的右兒子

---

push_up模板

先蓄蓄力，放松放松

void push_up ( int x ) {siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x]; }

---

split拆樹模板(按權(quán)值拆)

$split$拆樹的結(jié)果就是把樹根據(jù)要求值$k$拆成兩半

左邊全是值$\le k$的點(diǎn)，右邊全是值$>k$的點(diǎn)

上圖講解：充分運(yùn)用畫過的圖，我?guī)ьI(lǐng)大家走一遍，再不懂就不管本蒟蒻了

假設(shè)我們的$k$為35，那么首先從根節(jié)點(diǎn)1開始，發(fā)現(xiàn)1的權(quán)值25小于35

這個(gè)時(shí)候我們就能確定根節(jié)點(diǎn)以及根節(jié)點(diǎn)的左子樹的權(quán)值全都是小于35的

那么這個(gè)時(shí)候它們是屬于拆分后左邊的子樹的

但是我們會(huì)發(fā)現(xiàn)根節(jié)點(diǎn)的右子樹也存在可能值大于35的節(jié)點(diǎn)

我們就需要繼續(xù)往下拆分

接下來走到節(jié)點(diǎn)3，發(fā)現(xiàn)權(quán)值大于35，可以得出的結(jié)論是3節(jié)點(diǎn)以及它的右子樹的權(quán)值都是大于35的，應(yīng)該是屬于拆分后的右子樹，

但是同樣的我們不能肯定它的左兒子是否也是歸屬于右邊，繼續(xù)往左拆分

最后走到了葉子節(jié)點(diǎn)，發(fā)現(xiàn)節(jié)點(diǎn)4的權(quán)值小于等于35也應(yīng)該歸于左邊

這個(gè)時(shí)候就把節(jié)點(diǎn)4接到根節(jié)點(diǎn)1的右邊，成功把1和3的邊給斷掉

最后一層一層回溯，最頂層的兩個(gè)根節(jié)點(diǎn)就分別為1，3

節(jié)點(diǎn)1統(tǒng)領(lǐng)了所有權(quán)值小于等于$k$的子樹，節(jié)點(diǎn)3統(tǒng)領(lǐng)了所有權(quán)值大于$k$的子樹

我的寫法是傳地址，這樣就直接更改了

---

void split ( int p, int &l, int &r, int x ) {if ( ! p ) {l = r = 0;return;}if ( key[p] <= x ) {l = p;split ( son[p][1], son[p][1], r, x );push_up ( l );}else {r = p;split ( son[p][0], l, son[p][0], x );push_up ( r );} }

---

split拆樹模板(按個(gè)數(shù)拆)

此代碼有適用范圍！！！在某些題中會(huì)出錯(cuò)

按下標(biāo)拆的思路與按權(quán)值拆是一樣的，只不過往右子樹找的時(shí)候記得把左子樹和根占得位置給減掉即可

拆出來的左子樹的個(gè)數(shù)恰好是給定的$k$，右子樹就是剩下來的所有點(diǎn)

void split_id ( int p, int &l, int &r, int x ) {if ( ! p ) {l = r = 0;return;}if ( siz[son[p][0]] + 1 <= x ) {l = p;split_id ( son[p][1], son[p][1], r, x - siz[son[p][0]] - 1 );push_up ( l );}else {r = p;split_id ( son[p][0], l, son[p][0], x );push_up ( r );} }

---

merge合并模板（地址版）

我們可以發(fā)現(xiàn)拆分子樹的時(shí)候，改變了樹的形態(tài)，這也是無(wú)法進(jìn)行$treap$的旋轉(zhuǎn)操作的一個(gè)原因，
百因必有果，你的報(bào)應(yīng)就是我

既然方便了$split$拆分，改變了樹的形態(tài)，我們就必須再寫一個(gè)補(bǔ)丁函數(shù)，把樹進(jìn)行還原修復(fù)

但是我們不再是使用權(quán)值$k$進(jìn)行，我們思考$treap$用旋轉(zhuǎn)的目的是為了維護(hù)樹的鍵值不是從大到小就是從小到大

反正就是要有一定的順序

那么$merge$的目的也是維護(hù)樹的鍵值有順序

本來$split$拆的樹也是我們維護(hù)好了順序的

所以$merge$合并的時(shí)候根據(jù)鍵值順序來合并，也能還原$split$所拆的樹

在這里我仍然選擇的傳地址直接改在原來的地方，如果把上邊的$split$理解了，那么我相信這個(gè)也就很好理解了

void merge ( int &p, int x, int y ) {if ( ! x || ! y ) {p = x + y;return;}if ( rd[x] < rd[y] ) {p = x;merge ( son[p][1], son[p][1], y );}else {p = y;merge ( son[p][0], x, son[p][0] );}push_up ( p ); }

---

merge合并模板（帶返回根）

int merge ( int x, int y ) {if ( ! x || ! y )return x + y;if ( rd[x] < rd[y] ) {son[x][1] = merge ( son[x][1], y );push_up ( x );return x;}else {son[y][0] = merge ( x, son[y][0] );push_up ( y );return y;} }

---

區(qū)間模板

其實(shí)就是先把這個(gè)區(qū)間$[l,r]$拆出來然后搞一波，再把它合并回去

可以理解為先把部隊(duì)里某一個(gè)方陣的士兵扯出來再捅幾刀最后再讓他們歸隊(duì)，好殘忍

void XXX ( int x, int y ) {int l, r, L, R;spilt ( root, l, r, y );split ( l, L, R, x - 1 );//區(qū)間里面進(jìn)行的操作merge ( l, L, R );merge ( root, l, r ); }

我們以翻轉(zhuǎn)$reverse$為例，小聲bb：是為了讓你們做文藝平衡樹更簡(jiǎn)單

void reverse ( int x, int y ) {int l, r, L, R;spilt ( root, l, r, y );split ( l, L, R, x - 1 );lazy[R] = !lazy[R];//對(duì)[x,y]區(qū)間進(jìn)行打標(biāo)，1表示翻轉(zhuǎn)，0表示沒有翻轉(zhuǎn) merge ( l, L, R );merge ( root, l, r ); }

---

簡(jiǎn)單過渡一下：其實(shí)多做幾道題多用用模板會(huì)對(duì)代碼更加理解，為了方便各位理解下面更改的函數(shù)，在這里簡(jiǎn)單總結(jié)一下$split$和$merge$的思路

$split(root,l,r,x)$表示把以$root$為根的子樹按照權(quán)值$x$拆分，$l$存儲(chǔ)著小于等于$x$的子樹的根，$r$存儲(chǔ)著大于$x$的子樹的根

$merge(root,l,r)$表示把一棵子樹的根為$l$和另一棵子樹的根為$r$合并為一棵根為$root$的新根

那么其余的操作都可以用$split$和$merge$改變我們以前的寫法，新朋友就要多用用嘛！

---

insert插入模板

$insert$之前我們是用的遞歸方式，在這里就要充分運(yùn)用$split$和$merge$

我聲明一下，很多很多篇博客都是直接新建一個(gè)節(jié)點(diǎn)，本蒟蒻就不理解了，對(duì)于一個(gè)點(diǎn)它可能已經(jīng)出現(xiàn)在樹上了，這個(gè)時(shí)候就直接$cnt++$，為什么要選擇新建點(diǎn)呢？

所以我就費(fèi)了九牛二虎之力寫出了自己想要的模板

當(dāng)然對(duì)于某部分的題各個(gè)點(diǎn)之間是互不相同的，或其它特殊的要求，我的代碼就與大佬們成為一流的了，這個(gè)時(shí)候就可以刪掉我代碼中if的判斷即可，不刪也不影響，最多代碼長(zhǎng)了一丟丟而已啦~

• 首先我們把樹先拆成權(quán)值都$\le x$的子樹和權(quán)值都$>x$的子樹
• 再把權(quán)值$\le x$的子樹拆分成權(quán)值$\le x?1$的樹和權(quán)值$>x?1$也就是權(quán)值等于$x$的樹
• 接著我們就判斷儲(chǔ)存權(quán)值等于$x$的樹的節(jié)點(diǎn)是否為空，
  • 如果為空就意味著樹上并沒有該點(diǎn)，就新建一個(gè)點(diǎn)；
  • 否則就直接$cnt++$再$update$一下
• 拆了就要合并，我們?cè)趺床鸬木驮趺?strong>倒著并回去，很簡(jiǎn)單的，本蒟蒻都能自己打出來

void insert ( int x ) {int l, r, L, R;split ( root, l, r, x );split ( l, L, R, x - 1 );if ( R ) {cnt[R] ++;push_up ( R );merge ( l, L, R );merge ( root, l, r );}else {++ Size;cnt[Size] = siz[Size] = 1;rd[Size] = rand ();key[Size] = x;merge ( l, L, Size );merge ( root, l, r );} }

---

delete刪除模板

仿照$insert$的思路

• 先把值為$x$的這個(gè)點(diǎn)拆出來
• 接下來判斷如果這個(gè)點(diǎn)插入的次數(shù)是否大于1
  • 如果大于可以直接$cnt??$，該點(diǎn)不會(huì)消失，倒著合并回去；
  • 否則該點(diǎn)就應(yīng)該消失在樹上，我們可以通過不讓它參與合并，排擠它 ，那么它就不會(huì)出現(xiàn)在樹上了，直接把值小于等于$x?1$的樹和值大于$x$的樹合并即可
    

void delet ( int x ) {int l, r, L, R;split ( root, l, r, x );split ( l, L, R, x - 1 );if ( R && cnt[R] > 1 ) {cnt[R] --;push_up ( R );merge ( l, L, R );merge ( root, l, r );}elsemerge ( root, L, r ); }

---

剩下的查找其實(shí)是可以照搬的，但是我還是給大家分享一些其它的寫法吧！！

---

find_kth找第k大模板

這個(gè)我還是很喜歡這種寫法的，所以就不更改了

int find_kth ( int rt, int x ) {if ( siz[son[rt][0]] >= x )return find_kth ( son[rt][0], x );else if ( siz[son[rt][0]] + cnt[rt] < x )return find_kth ( son[rt][1], x - siz[son[rt][0]] - cnt[rt] );elsereturn key[rt]; } //非遞歸結(jié)構(gòu)體版本 ↓ void find_val( int x ) {int now = rt;while( 1 ) {if( x <= t[t[now].lson].siz ) now = t[now].lson;else if( x <= t[t[now].lson].siz + t[now].cnt ) break;else x -= ( t[t[now].lson].siz + t[now].cnt ), now = t[now].rson;}printf( "%d\n", t[now].val ); }

Upd：
下面求排名為 $x$ 的數(shù)的方法不一定是對(duì)的。
因?yàn)榘凑諅€(gè)數(shù)大小分裂代碼的正確性當(dāng)且僅當(dāng)數(shù)據(jù)中每個(gè)數(shù)互不相等。
顯然，設(shè)想某個(gè)數(shù)有若干個(gè)，占據(jù)了排名為一段的區(qū)間，如果按照 $x/x?1$ 的個(gè)數(shù)分，全都劃在該數(shù)身上，則 $R$ 就是個(gè)空子樹了。
如果直接判 $R$ 是否為空也是錯(cuò)誤的。
但是我也不知道為什么？？！！所以還是麻煩大家寫上面的方法。
也有可能是因?yàn)椴┲鞯钠渌０迥承┫拗瓢选！！?br /> 數(shù)據(jù)結(jié)構(gòu)真是一個(gè)比一個(gè)玄學(xué)！！凸(艸皿艸 )

void find_val( int x ) {int l, r, L, R;split_siz( rt, x, l, r );split_siz( l, x - 1, L, R );printf( "%d\n", t[R].val );rt = merge( merge( L, R ), r ); }

---

get_rank找排名模板

我們就充分運(yùn)用新學(xué)函數(shù)，思考一下如果把$\le x?1$的樹拆出來
那么它的大小$+1$是不是就是$x$的$rank$排名呢！！！實(shí)在是

void get_rank ( int x ) {int l, r;split ( root, l, r, x - 1 );printf ( "%d\n", siz[l] + 1 );merge ( root, l, r ); }

---

pre找前驅(qū)模板

找前驅(qū)，這里是嚴(yán)格小于的情況，先拆分一下看有木有權(quán)值小于$x$的點(diǎn)
有的話我們就調(diào)用$find$_$kth$在拆分出來的那棵子樹中去找最后一個(gè)也就是$x$的前一個(gè)

int pre ( int x ) {int l, r, result;split ( root, l, r, x - 1 );if ( siz[l] )result = find_kth ( l, siz[l] );elseresult = INF;merge ( root, l, r );return result; }

---

suf找后驅(qū)模板

找后驅(qū)，與找前驅(qū)相似，這里是嚴(yán)格大于的情況，先拆分一下看有木有權(quán)值大于$x$的點(diǎn)
有的話我們就調(diào)用$find$_$kth$在拆分出來的那棵子樹中去找第一個(gè)也就是$x$的后一個(gè)

int suf ( int x ) {int l, r, result;split ( root, l, r, x );if ( siz[r] )result = find_kth ( r, 1 );elseresult = INF;merge ( root, l, r );return result; }

Upd：當(dāng)然你可以直接暴力的裂開。以找前驅(qū)為例，把 $\le x?1$ 的子樹列出來，從子樹的根開始瘋狂走右兒子（如果有）。

void find_pre( int x ) {int l, r;split_val( rt, x - 1, l, r );int now = l;while( t[now].rson ) now = t[now].rson;printf( "%d\n", t[now].val );rt = merge( l, r ); }void find_suf( int x ) {int l, r;split_val( rt, x, l, r );int now = r;while( t[now].lson ) now = t[now].lson;printf( "%d\n", t[now].val );rt = merge( l, r ); }

---

老套路來些題目練習(xí)練習(xí)，實(shí)在是太模板了，直接器官移植都能過，哎╮(╯▽╰)╭

例題1：普通平衡樹

題目

點(diǎn)擊查看

代碼實(shí)現(xiàn)

一樣一樣的，進(jìn)行器官移植即可

#include <cstdio> #include <algorithm> using namespace std; #define MAXN 100005 #define INF 0x7f7f7f7f int root, n, Size; int son[MAXN][2], cnt[MAXN], siz[MAXN], rd[MAXN], key[MAXN];void push_up ( int x ) {siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x]; }void split ( int p, int &l, int &r, int x ) {if ( ! p ) {l = r = 0;return;}if ( key[p] <= x ) {l = p;split ( son[p][1], son[p][1], r, x );push_up ( l );}else {r = p;split ( son[p][0], l, son[p][0], x );push_up ( r );} }void merge ( int &p, int x, int y ) {if ( ! x || ! y ) {p = x + y;return;}if ( rd[x] < rd[y] ) {p = x;merge ( son[p][1], son[p][1], y );}else {p = y;merge ( son[p][0], x, son[p][0] );}push_up ( p ); }void insert ( int x ) {int l, r, L, R;split ( root, l, r, x );split ( l, L, R, x - 1 );if ( R ) {cnt[R] ++;push_up ( R );merge ( l, L, R );merge ( root, l, r );}else {++ Size;cnt[Size] = siz[Size] = 1;rd[Size] = rand ();key[Size] = x;merge ( l, L, Size );merge ( root, l, r );} }void delet ( int x ) {int l, r, L, R;split ( root, l, r, x );split ( l, L, R, x - 1 );if ( R && cnt[R] > 1 ) {cnt[R] --;push_up ( R );merge ( l, L, R );merge ( root, l, r );}elsemerge ( root, L, r ); }int find_kth ( int rt, int x ) {if ( siz[son[rt][0]] >= x )return find_kth ( son[rt][0], x );else if ( siz[son[rt][0]] + cnt[rt] < x )return find_kth ( son[rt][1], x - siz[son[rt][0]] - cnt[rt] );elsereturn key[rt]; }int pre ( int x ) {int l, r, result;split ( root, l, r, x - 1 );if ( siz[l] )result = find_kth ( l, siz[l] );elseresult = INF;merge ( root, l, r );return result; }int suf ( int x ) {int l, r, result;split ( root, l, r, x );if ( siz[r] )result = find_kth ( r, 1 );elseresult = INF;merge ( root, l, r );return result; }void get_rank ( int x ) {int l, r;split ( root, l, r, x - 1 );printf ( "%d\n", siz[l] + 1 );merge ( root, l, r ); }int main() {scanf ( "%d", &n );while ( n -- ) {int opt, x;scanf ( "%d %d", &opt, &x );switch ( opt ) {case 1 : insert ( x ); break;case 2 : delet ( x ); break;case 3 : get_rank ( x ); break;case 4 : printf ( "%d\n", find_kth ( root, x ) ); break;case 5 : printf ( "%d\n", pre ( x ) ); break;case 6 : printf ( "%d\n", suf ( x ) ); break;}}return 0; }

例題2：文藝線段樹

題目

點(diǎn)擊查看題目

代碼實(shí)現(xiàn)

在這里因?yàn)樯婕暗揭粋€(gè)區(qū)間翻轉(zhuǎn)問題，我們就可以類比線段樹打$lazy$標(biāo)記，也對(duì)$treap$樹打一個(gè)標(biāo)記
那么在我們進(jìn)行$split,merge$操作時(shí)，要保證對(duì)于一個(gè)點(diǎn)，它的左兒子和右兒子是對(duì)的，所以這里要寫一個(gè)標(biāo)記下放的$pushdown$
最后輸出數(shù)列的時(shí)候也采用遞歸的方式，左中右的中序遍歷，在這之間順便進(jìn)行標(biāo)記下放

#include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define MAXN 100005 #define INF 0x7f7f7f7f int root, n, Size, m; int son[MAXN][2], cnt[MAXN], siz[MAXN], rd[MAXN], key[MAXN]; bool lazy[MAXN];void push_up ( int x ) {siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x]; }void pushdown ( int x ) {if ( x && lazy[x] ) {swap ( son[x][0], son[x][1] );lazy[son[x][0]] = !lazy[son[x][0]];lazy[son[x][1]] = !lazy[son[x][1]];lazy[x] = 0;return; } }void split ( int p, int &l, int &r, int x ) {if ( ! p ) {l = r = 0;return;}pushdown ( p );//千萬(wàn)不要放在if-else里面，先把標(biāo)記下放去交換左右兒子//確保此時(shí)p的左右兒子是真的，不然就報(bào)錯(cuò)了/(ㄒoㄒ)/~~if ( siz[son[p][0]] + 1 <= x ) {l = p;split ( son[p][1], son[p][1], r, x - siz[son[p][0]] - 1 );push_up ( l );}else {r = p;split ( son[p][0], l, son[p][0], x );push_up ( r );} }void merge ( int &p, int x, int y ) {if ( ! x || ! y ) {p = x + y;return;}if ( rd[x] < rd[y] ) {pushdown ( x );p = x;merge ( son[p][1], son[p][1], y );}else {pushdown ( y );p = y;merge ( son[p][0], x, son[p][0] );}push_up ( p ); }void insert ( int x ) {int l, r, L, R;split ( root, l, r, x );split ( l, L, R, x - 1 );if ( R ) {cnt[R] ++;push_up ( R );merge ( l, L, R );merge ( root, l, r );}else {++ Size;cnt[Size] = siz[Size] = 1;rd[Size] = rand ();key[Size] = x;merge ( l, L, Size );merge ( root, l, r );} }void delet ( int x ) {int l, r, L, R;split ( root, l, r, x );split ( l, L, R, x - 1 );if ( R && cnt[R] > 1 ) {cnt[R] --;push_up ( R );merge ( l, L, R );merge ( root, l, r );}elsemerge ( root, L, r ); }void print ( int x ) {if ( ! x )return;pushdown ( x );print ( son[x][0] );printf ( "%d ", key[x] );print ( son[x][1] ); }void reverse ( int x, int y ) {int l, r, L, R;split ( root, l, r, y );split ( l, L, R, x - 1 );lazy[R] = !lazy[R];merge ( l, L, R );merge ( root, l, r ); }int main() {scanf ( "%d %d", &n, &m );for ( int i = 1;i <= n;i ++ )insert ( i );for ( int i = 1;i <= m;i ++ ) {int idl, idr;scanf ( "%d %d", &idl, &idr );reverse ( idl, idr );}print ( root );return 0; }

因此這道題啟示我們，隨著我們的操作要求的不一樣，在$split$和$merge$中一些語(yǔ)句可能會(huì)發(fā)生順序變換，不能盲目地去背模板，一定要理解

可能會(huì)有部分代碼細(xì)節(jié)錯(cuò)誤，因?yàn)檫@些題實(shí)在是水，導(dǎo)致有些寫錯(cuò)的代碼還是能跑過數(shù)據(jù)

---

總結(jié)

以上是生活随笔為你收集整理的[非旋平衡树]fhq_treap概念及模板，例题：普通平衡树，文艺线段树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。