平衡樹 - FHQ 學(xué)習(xí)筆記

主要參考萬萬沒想到 的 FHQ-Treap學(xué)習(xí)筆記。

本片文章的姊妹篇：平衡樹 - Splay 學(xué)習(xí)筆記。

感覺完全不會平衡樹，又重新學(xué)習(xí)了一遍 FHQ，一口氣把常見套路都學(xué)完了。

一、大致內(nèi)容及分類

FHQ(???)，全稱非旋轉(zhuǎn) Treap，是一種可以用于維護(hù)按權(quán)值、排名分裂的數(shù)據(jù)結(jié)構(gòu)。它相比與 Splay 雖然常數(shù)較大，但是實現(xiàn)起來代碼難度相對容易，而且由于它非旋的特點，也可以用來實現(xiàn)可持久化。

既然叫做非旋 Treap，它兼有 Treap 的特點又有非旋轉(zhuǎn)獨特的優(yōu)勢。

• 從 Treap 角度看，他們同樣都是依賴修正值 rnd 是隨機(jī)的，用將他們按照 rnd 形成一個小根堆。與 Treap 相同，它也滿足笛卡爾樹的性質(zhì)，它的中序遍歷和它的插入順序相同，即 \(1\) 到 \(n\) 的序列。
• 從非旋角度看，FHQ 直接通過 split 和 merge 操作實現(xiàn)添加、刪除元素，不用再樹上旋轉(zhuǎn)了。

根據(jù)不同題目要求，將平衡樹分為序列平衡樹和權(quán)值平衡樹。

• 序列平衡樹的中序遍歷為每個元素在序列中的下標(biāo)，權(quán)值為每個元素具體的值，常見題型為區(qū)間翻轉(zhuǎn)等。
• 權(quán)值平衡樹的中序遍歷是所有元素從小到大排序，即按照中序遍歷提取所有元素后元素權(quán)值遞增，常見操作為第 \(k\) 大等。

如果毒瘤出題人同時綜合了以上兩種操作，即區(qū)間翻轉(zhuǎn) \(+\) 區(qū)間第 \(k\) 大，應(yīng)該怎么做呢？好吧，如果真是這樣，這篇文章可能不能夠幫到你，直接上一個根號做法！

二、基本操作

FHQ 的核心操作就是 split 出操作區(qū)間，操作完后 merge 回去。

下邊講解中默認(rèn)的平衡樹類型為權(quán)值平衡樹，序列平衡樹其實是將某些 \(val\) 改為了 \(siz\)。

分裂 split

無論是按照排名還是權(quán)值分裂，他們都是將原樹分為左右兩半，可以利用中序遍歷的性質(zhì)進(jìn)行分裂。

具體操作時，我們新建兩個臨時變量 \(x,y\) 分別表示分裂出來的左邊、右邊的那顆平衡樹。

如果我們遇到一個應(yīng)該屬于 \(x\) 樹的節(jié)點，就將這個點以及這個點的左子樹加入 \(x\) 樹中，并遞歸分裂右子樹；如果遇到屬于 \(y\) 的，就將這個點與它的右子樹加入 \(y\) 樹中，并遞歸分裂左子樹。

需要注意到是，如果使用序列平衡樹，下面和 \(k\) 的大小判斷應(yīng)該變?yōu)?\(ls.siz+1\le k\)。

\(\bigstar\texttt{Attention}\)：如果需要 split 一個區(qū)間，記得先 split 右端點再 split 左端點！

可以寫出偽代碼如下：

void split(int p,int k,int &x,int &y) // 分裂出 (-infty,k],(k,+infty) {if(!p) { x=y=0; return; }pushdown(p);if(tree[p].val<=k) x=p,split(rs,k,rs,y);else y=p,split(ls,k,x,ls);pushup(p); }

合并 merge

由于這是 FHQ 的 merge，需要在合并時既保證小根堆性質(zhì)又不破壞中序遍歷的特點，對合并的兩棵樹有特殊的要求：左右區(qū)間不能夠相交或者順序顛倒！

所以我們在合并時必須按照順序從左到右合并。

具體操作時，可以直接將 rnd 小的作為新樹的根節(jié)點，如果這個根節(jié)點來自左子樹就遞歸右子樹，相反來自右子樹就遞歸左子樹(由于滿足上面區(qū)間不相交也不顛倒的特點)。

寫出偽代碼：

int merge(int x,int y) {if(!x || !y) return x+y;if(tree[x].rnd<tree[y].rnd){ pushdown(x),tree[x].pr=merge(tree[x].pr,y),pushup(x); return x; }else{ pushdown(y),tree[y].pl=merge(x,tree[y].pl),pushup(y); return y; } }

新建節(jié)點 new

沒什么可說的，就是給新節(jié)點附一個隨機(jī)的 rnd。

inline int New(ll Val) {int p=++All;tree[p].rnd=rand(),tree[p].val=Val;tree[p].siz=tree[p].cnt=1;tree[p].pl=tree[p].pr=0;return p; }

插入 insert

直接分裂出兩端區(qū)間，把新建的加點放到兩棵樹中間在合并即可。

inline void Insert(ll Val) {split(root,Val,x,y);root=merge(merge(x,New(Val)),y); }

刪除 delete

FHQ 可以實現(xiàn)刪除一個數(shù)或刪除這個值的所有數(shù)，唯一區(qū)別就在于分裂時的不同。

inline void Delete_one(ll Val) {split(root,Val,x,z),split(x,Val-1,x,y);y=merge(tree[y].pl,tree[y].pr);root=merge(merge(x,y),z); } inline void Delete_All(ll Val) {split(root,Val,x,z),split(x,Val-1,x,y);root=merge(x,z); }

查詢排名對應(yīng)權(quán)值 Rank_to_Value

根據(jù)每顆子樹的 \(siz\) 暴力跳即可。

inline int kth(int p,int Rank) // 這里返回的是找到節(jié)點的下標(biāo) {while(p){if(tree[ls].siz>=Rank) p=ls;else if(tree[ls].siz+tree[p].cnt>=Rank) return p;else Rank-=tree[ls].siz+tree[p].cnt,p=rs;}return p; }

查詢權(quán)值對應(yīng)排名 Value_to_Rank

按照權(quán)值分裂出來后左區(qū)間樹的 \(siz\) 就是排名。

inline int Value_to_Rank(ll Value) {split(root,Value-1,x,y);int ret=tree[x].siz+1;root=merge(x,y);return ret; }

查詢前驅(qū) Findpre

分裂出來后在左子樹中排名最靠后的是前驅(qū)。

inline ll Findpre(ll Value) {split(root,Value-1,x,y);ll ret=tree[kth(x,tree[x].siz)].val;root=merge(x,y);return ret; }

查詢后繼 Findnex

分裂出來后在右子樹中排名最靠前的是后繼。

inline ll Findnex(ll Value) {split(root,Value,x,y);ll ret=tree[kth(y,1)].val;root=merge(x,y);return ret; }

三、可持久化平衡樹

平衡樹上的可持久化和線段樹的可持久化其實差別不大，每次修改的時候需要建立新的節(jié)點，對于每個版本也需要保存根節(jié)點。

新建一個點的原則：如果我們把版本最新的點叫做新點，那么我們只能夠在可持久化平衡樹中對新點修改，不然就會出錯，所以在 split 與 merge 中，我們一旦對一個值進(jìn)行了修改，就需要新建一個節(jié)點。

偽代碼如下：

inline void pushdown(int p) {if(!tree[p].tag) return;if(ls) ls=clone(ls),tree[ls].tag^=1,swap(tree[ls].pl,tree[ls].pr);if(rs) rs=clone(rs),tree[rs].tag^=1,swap(tree[rs].pl,tree[rs].pr);tree[p].tag=false; } inline int clone(int p) { tree[++All]=tree[p]; return All; } void split(int p,ll k,int &x,int &y) {if(!p) { x=y=0; return; }pushdown(p);if(tree[p].val<=k) x=clone(p),split(rs,k,tree[x].pr,y),pushup(x);else y=clone(p),split(ls,k,x,tree[y].pl),pushup(y); } int merge(int x,int y) {if(!x || !y) return x+y;if(tree[x].rnd<tree[y].rnd){pushdown(x),x=clone(x),tree[x].pr=merge(tree[x].pr,y),pushup(x);return x;}else{pushdown(y),y=clone(y),tree[y].pl=merge(x,tree[y].pl),pushup(y);return y;} }

四、常見優(yōu)化技巧

垃圾回收

在每次新建節(jié)點的時候先從垃圾桶中撿，如果垃圾撿光了再新開節(jié)點。

笛卡爾樹方式建樹

由于我們的 FHQ 是一種笛卡爾樹，所以如果給定了一堆點，完全可以直接用笛卡爾樹的方式 \(\mathcal{O(n)}\) 建樹。

inline int build() {int tp=0,p=0,Last;for(int i=1;i<=n;i++){p=New(v[i]),Last=0;while(tp && tree[sta[tp]].rnd>tree[p].rnd) pushup(Last=sta[tp--]);if(tp) tree[sta[tp]].pr=p;tree[p].pl=Last,sta[++tp]=p;}while(tp) pushup(sta[tp--]);return sta[1]; }

定期重構(gòu)

如果題目中對空間有限制而且不要求查詢歷史版本，可以定期重構(gòu)。當(dāng)使用的空間超過一定值的時候，我們中序遍歷整棵樹并放入數(shù)組中，在線性建樹。

啟發(fā)式合并

如果需要合并兩個有交集的 Treap 時該怎么做？我們可以每次將較小的數(shù)合并到較大的樹中去，這樣每個點最多只會合并 \(\log n\) 次，每次合并復(fù)雜度 \(n\log n\)，總時間復(fù)雜度 \(\mathcal{O(n\log ^2 n)}\)。

區(qū)間縮點

詳見萬萬沒想到的博客，咕咕咕。

五、模板

struct FHQ_number {#define Maxn 點數(shù)#define ls tree[p].pl#define rs tree[p].prprivate:int All=0,root=0;struct NODE { int pl,pr,siz,cnt,rnd; ll val; };NODE tree[Maxn];inline int Dot() { return ++All; }inline int New(ll Val){int p=Dot();tree[p].rnd=rand(),tree[p].val=Val;tree[p].siz=tree[p].cnt=1;tree[p].pl=tree[p].pr=0;return p;}inline void pushdown(int p) { p--; }inline void pushup(int p){ tree[p].siz=tree[ls].siz+tree[rs].siz+tree[p].cnt; }void split(int p,int k,int &x,int &y){if(!p) { x=y=0; return; }pushdown(p);if(tree[p].val<=k) x=p,split(rs,k,rs,y);else y=p,split(ls,k,x,ls);pushup(p);}int merge(int x,int y){if(!x || !y) return x+y;if(tree[x].rnd<tree[y].rnd){pushdown(x),tree[x].pr=merge(tree[x].pr,y),pushup(x);return x;}else{pushdown(y),tree[y].pl=merge(x,tree[y].pl),pushup(y);return y;}}inline int kth(int p,int Rank){while(p){if(tree[ls].siz>=Rank) p=ls;else if(tree[ls].siz+tree[p].cnt>=Rank) return p;else Rank-=tree[ls].siz+tree[p].cnt,p=rs;}return p;}int x,y,z;public:inline void Insert(ll Val){ split(root,Val,x,y),root=merge(merge(x,New(Val)),y); }inline void Delete_one(int Val){split(root,Val,x,z),split(x,Val-1,x,y);y=merge(tree[y].pl,tree[y].pr);root=merge(merge(x,y),z);}inline ll Rank_to_Value(int Rank){ return tree[kth(root,Rank)].val; }inline int Value_to_Rank(ll Value){split(root,Value-1,x,y);int ret=tree[x].siz+1;root=merge(x,y);return ret;}inline ll Findpre(ll Value){split(root,Value-1,x,y);ll ret=tree[kth(x,tree[x].siz)].val;root=merge(x,y);return ret;}inline ll Findnex(ll Value){split(root,Value,x,y);ll ret=tree[kth(y,1)].val;root=merge(x,y);return ret;} }T; struct FHQ_sequence {#define Maxn 點數(shù)#define ls tree[p].pl#define rs tree[p].print All=0,root=0;struct NODE { int pl,pr,siz,cnt,rnd,val; bool tag; };NODE tree[Maxn];inline int Dot() { return ++All; }inline int New(int Val){int p=Dot();tree[p].rnd=rand(),tree[p].val=Val;tree[p].cnt=tree[p].siz=1;tree[p].pl=tree[p].pr=0;return p;}inline void pushdown(int p){if(!tree[p].tag) return;swap(tree[ls].pl,tree[ls].pr);swap(tree[rs].pl,tree[rs].pr);tree[ls].tag^=1,tree[rs].tag^=1;tree[p].tag=false;}inline void pushup(int p){ tree[p].siz=tree[ls].siz+tree[p].cnt+tree[rs].siz; }void split(int p,int k,int &x,int &y){if(!p) { x=y=0; return; }pushdown(p);if(tree[ls].siz<k) x=p,split(rs,k-tree[ls].siz-1,rs,y);else y=p,split(ls,k,x,ls);pushup(p);}int merge(int x,int y){if(!x || !y) return x+y;if(tree[x].rnd<tree[y].rnd){pushdown(x),tree[x].pr=merge(tree[x].pr,y),pushup(x);return x;}else{pushdown(y),tree[y].pl=merge(x,tree[y].pl),pushup(y);return y;}}int kth(int p,int Rank){while(p){if(tree[ls].siz>=Rank) p=ls;else if(tree[ls].siz+tree[p].cnt>=Rank) return p;else Rank-=tree[ls].siz+tree[p].cnt,p=ls;}return p;}void Insert(int Val) // 插到末尾 { root=merge(root,New(Val)); }int x,y,z;inline void Reverse(int l,int r){split(root,r,x,z),split(x,l-1,x,y);swap(tree[y].pl,tree[y].pr),tree[y].tag^=1;root=merge(merge(x,y),z);}void print(int p){pushdown(p);if(ls) print(ls);printf("%d ",tree[p].val);if(rs) print(rs);} }T;

六、例題

【模板】普通平衡樹

【模板】普通平衡樹(數(shù)據(jù)加強(qiáng)版)

【模板】文藝平衡樹

【模板】可持久化平衡樹

【模板】可持久化文藝平衡樹

平衡樹題單

總結(jié)

以上是生活随笔為你收集整理的平衡树 - FHQ 学习笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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