【數據結構】平衡樹splay和fhq—treap
1.BST二叉搜索樹
顧名思義，它是一棵二叉樹。
它滿足一個性質：每一個節點的權值大於它的左兒子，小於它的右兒子。
當然不只上面那兩種樹的結構。
那麼根據性質，可以得到該節點左子樹里的所有值都比它小，右子樹的都比它大。
而平衡樹都是基於BST的。
為什麼叫做平衡樹？對於數的操作可能會破壞BST的性質，這時會進行另外的操作，保持它的性質。
為什麼要用BST?對於一棵BST，每一次的操作，都相當於進行一次二分，時間複雜度可以降到log級別。
這裡寫的是兩個常用的平衡樹。
2.Splay
splay樹是基於一個rotate（旋轉）函數和splay（伸展）函數來保證平衡。
初始化
struct Splay_Tree{int son[2],fa,size,cnt,val;}T[N]; #define ls(x) T[x].son[0]//左兒子 #define rs(x) T[x].son[1]//右兒子 #define fa(x) T[x].fa//當前點他爹 #define sze(x) T[x].size//以當前點為根的樹的大小 #define cnt(x) T[x].cnt//當前點的出現次數 #define val(x) T[x].val//當前點的權值 //不為別的，小括弧看起來爽一點
rotate
例如，我們要將下圖的x點右旋：
可以手推一下，總結：
rotate要影響3個點：x，y（x的父親），z（y的父親，x的爺爺）；
y是z的k兒子（k用來判斷左兒子，還是右兒子，0是左兒子，1是右兒子，用^1進行切換），則x就變成z的k兒子；
x的k^1兒子變成y的k兒子，y變成x的k^1兒子。
（想不到怎麼描述了，只能這麼瞎逼逼）
inline void rotate(int x){ int y=fa(x),z=fa(y); int k=(rs(y)==x),w=T[x].son[k^1]; T[z].son[rs(z)==y]=x,fa(x)=z; T[y].son[k]=w,fa(w)=y; T[x].son[k^1]=y,fa(y)=x; update(y),update(x); }
update就是個實時更新
splay
這一步是要將x點旋轉到goal的兒子的位置
那麼怎麼做呢?循環就行了。但是還有一種特殊情況，由於這種情況都滿足被旋轉點和父節點都是左節點或者是右兒子，我們姑且稱它為三點一線，先看圖：
比如說我們這裡要splay④，如果直接把④一直旋轉到根節點的話就會是這樣：
可以看見③還是①的左節點，相當於只是改變了④和①的關係，專業一點就是說形成了單旋使平衡樹失衡。而解決的方法就是在出現三點一線時先旋轉它的父節點避免單旋，正確的應該是這樣：
inline void splay(int x,int goal){ while(fa(x)!=goal){ int y=fa(x),z=fa(y); if(z!=goal) (y==ls(z))^(x==ls(y))?rotate(x):rotate(y); rotate(x); } if(!goal) root=x; }
insert
我們要先從根節點一直向下找到該插入的位置，若該節點已存在，cnt++就行，否則造一個新的點，別忘了splay保證平衡：
inline void insert(int x){ int u=root,father=0; while(u&&val(u)!=x){ father=u; u=T[u].son[x>val(u)]; } if(u) cnt(u)++; else{ u=++tot; if(father) T[father].son[x>val(u)]=u; ls(u)=rs(u)=0;fa(u)=father,val(u)=x,cnt(u)=sze(u)=1; } splay(u,0); }
find
這是找到權值為val的點的位置，程式碼很好理解：
inline void find(int x){ int u=root; if(!u) return ; while(t[u].son[x>t[u].val]&&x!=t[u].val) u=t[u].son[x>t[u].val]; splay(u,0); }
search
找前後驅。這裡都打在了一個函數里，用0表示找前驅，1找後驅。
inline int search(int x,int tmp){//找前後驅 find(x); int u=root; if(t[u].val<x&&!tmp) return u; if(t[u].val>x&&tmp) return u; u=t[u].son[tmp]; while(t[u].son[tmp^1]) u=t[u].son[tmp^1]; //這裡蛇皮走位，而不是一直大或者一直小 return u; }
delete
刪除操作。先找到前後驅，將前驅旋轉至根，而將後驅旋轉至前驅的右兒子。
這時要刪除的點就單獨的呆在了後驅的左兒子的位置。
如果cnt>1，cnt–；否則將該點變為0
inline void delet(int x){ int pre=search(x,0),suf=search(x,1); splay(pre,0),splay(suf,pre); int del=t[suf].son[0]; if(t[del].cnt>1){t[del].cnt--;splay(del,0);} else t[suf].son[0]=0; }
排名詢問
find一遍，x的左兒子的大小+1就是排名
第k大的數
自根向下找，很好理解：
inline int search_value(int x){ int u=root; if(t[u].size<x) return 0; while(1){ int v=t[u].son[0]; if(x>t[v].size+t[u].cnt){ x-=t[v].size+t[u].cnt; u=t[u].son[1]; } else if(t[v].size>=x) u=v; else return t[u].val; } }
就是把上面的函數給混在一起：
#include<cstdio> using namespace std; const int maxn=201000; int root,tot; struct tree{int son[2],fa,cnt,val,size;}t[maxn]; inline void update(int x){t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+t[x].cnt;} inline void rotate(int x){ int y=t[x].fa,z=t[y].fa; int k=(t[y].son[1]==x); t[z].son[(t[z].son[1]==y)]=x; t[x].fa=z; t[y].son[k]=t[x].son[k^1]; t[t[x].son[k^1]].fa=y; t[x].son[k^1]=y; t[y].fa=x; update(y),update(x); } inline void splay(int x,int goal){ while(t[x].fa!=goal){ int y=t[x].fa,z=t[y].fa; if(z!=goal) (t[z].son[0]==y)^(t[y].son[0]==x)?rotate(x):rotate(y); rotate(x); } if(!goal) root=x; } inline void find(int x){ int u=root; if(!u) return ; while(t[u].son[x>t[u].val]&&x!=t[u].val) u=t[u].son[x>t[u].val]; splay(u,0); } inline void insert(int x){ int u=root,father=0; while(u&&t[u].val!=x){ father=u; u=t[u].son[x>t[u].val]; } if(u) t[u].cnt++; else{ u=++tot; if(father) t[father].son[x>t[father].val]=u; t[u].son[0]=t[u].son[1]=0; t[tot].fa=father,t[tot].val=x,t[tot].cnt=t[tot].size=1; } splay(u,0); } inline int search(int x,int tmp){//找前後驅 find(x); int u=root; if(t[u].val<x&&!tmp) return u; if(t[u].val>x&&tmp) return u; u=t[u].son[tmp]; while(t[u].son[tmp^1]) u=t[u].son[tmp^1]; return u; } inline void delet(int x){ int pre=search(x,0),suf=search(x,1); splay(pre,0),splay(suf,pre); int del=t[suf].son[0]; if(t[del].cnt>1){t[del].cnt--;splay(del,0);} else t[suf].son[0]=0; } inline int search_value(int x){ int u=root; if(t[u].size<x) return 0; while(1){ int v=t[u].son[0]; if(x>t[v].size+t[u].cnt){ x-=t[v].size+t[u].cnt; u=t[u].son[1]; } else if(t[v].size>=x) u=v; else return t[u].val; } } signed main(){ int n;scanf("%d",&n); insert(1e9),insert(-1e9); while(n--){ int opt,x; scanf("%d%d",&opt,&x); if(opt==1) insert(x); if(opt==2) delet(x); if(opt==3){ find(x);printf("%d\n",t[t[root].son[0]].size);} if(opt==4) printf("%d\n",search_value(x+1)); if(opt==5) printf("%d\n",t[search(x,0)].val); if(opt==6) printf("%d\n",t[search(x,1)].val); } return 0; }
Splay
區間操作
其實思想類似於線段樹，找到那個區間，對那個區間進行操作
#include<cstdio> #include<algorithm> using namespace std; inline int read(){ int sum=0;bool flag=true;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')flag=false;ch=getchar();} while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();} return (flag?sum:-sum); } inline void print(int x){ if(x<0) putchar('-'),x=-x; while(x>=10) print(x/10); putchar(x%10+'0'); } const int maxn=101000; int root,tot,tag[maxn],key[maxn],ans[maxn]; struct tree{int son[2],fa,cnt,val,size;}t[maxn]; inline void update(int x){t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+1;} inline void pushdown(int x){ if(tag[x]){ tag[t[x].son[0]]^=1,tag[t[x].son[1]]^=1; swap(t[x].son[0],t[x].son[1]); tag[x]=0; } } inline int getson(int x){return t[t[x].fa].son[1]==x;} inline void rotate(int x){ int y=t[x].fa,z=t[y].fa,tt=getson(x); if(z) t[z].son[getson(y)]=x; else root=x; t[x].fa=z; int tmp=t[x].son[!tt]; if(tmp) t[tmp].fa=y; t[y].son[tt]=tmp; t[x].son[!tt]=y; t[y].fa=x; update(y),update(x); } inline void splay(int x,int goal){ while(t[x].fa!=goal){ int y=t[x].fa,z=t[y].fa; if(z!=goal) (getson(y)==getson(x))?rotate(y):rotate(x); rotate(x); } } inline int find(int x){ int u=root; while(1){ pushdown(u); if(t[u].son[0]&&x<=t[t[u].son[0]].size) u=t[u].son[0]; else{ int tmp=(t[u].son[0]?t[t[u].son[0]].size:0)+1; if(x==tmp) return u; x-=tmp; u=t[u].son[1]; } } } inline int build(int l,int r,int tmp){ int mid=(l+r)>>1; t[mid].fa=tmp; key[mid]=ans[mid]; if(l<mid) t[mid].son[0]=build(l,mid-1,mid); if(r>mid) t[mid].son[1]=build(mid+1,r,mid); update(mid); return mid; } inline void work(int x){ pushdown(x); if(t[x].son[0]) work(t[x].son[0]); ans[++tot]=key[x]; if(t[x].son[1]) work(t[x].son[1]); } signed main(){ int n=read(),m=read(); for(int i=1;i<=n+2;i++) ans[i]=i-1; root=build(1,n+2,0); while(m--){ int l=read(),r=read(); l=find(l),r=find(r+2); splay(l,0);splay(r,l); tag[t[t[root].son[1]].son[0]]^=1; } work(root); for(int i=1;i<=n;i++) printf("%d ",ans[i+1]); return 0; }
文藝平衡樹
3*.Treap
Treap是Tree和Heap,所以很明顯有heap（堆）的性質。
怎樣保證BST的性質的同時保證堆的性質？
對每一個節點，有兩個值，一個是權值，另一個是rnd隨機值，來決定優先順序。
而兩個同時限制，那麼旋轉時會很麻煩。
對，所以我沒學。淦~~~
但其實會了splay和fhq—treap，這個treap也沒有學習的必要了
對了，機房大佬表示Treap是真的菜
4.fhq-Treap
名字叫treap，但和treap之間的相同處，也只是同為帶有隨機附加域滿足堆的性質的二叉搜索樹。
FHQ-Treap,又名非旋Treap,是范浩強大爺在某些奇特的靈感之下發明的一種平衡樹
這裡只需要了解2個主要操作，便可處理很多問題，包括可持久化。
split（分解）和merge（合併）
還需要運用2個另外的樹，x和y，只是用來記錄臨時分裂的兩棵樹的根節點，因為樹無旋，所以根節點下的樹唯一確定。
split
遞歸進行分解，比該點權值小的放在x樹上，比它大的放在y樹上，同時實時更新。
當然權值分裂後還有排名（rnd值）分裂，這裡只放了權值分裂。
inline void split(int id,int k,int &x,int &y){ if(!id){x=y=0;return ;} if(val[id]<=k){ x=id; split(rs(id),k,rs(id),y); } else{ y=id; split(ls(id),k,x,ls(id)); } update(id); }
merge
首先merge操作是有前提條件的,要求是必須第一顆樹權值最大的節點要小於第二棵樹權值最小的節點 ，那麼我們就比較它們的隨機權值。如果rnd[l]<rnd[r]，我們就保留它的左子樹，另一棵樹作為它的右子樹；如果rnd[l]>=rnd[r]，那我們可以保留第二棵樹的右子樹，另一顆樹作為它的左子樹。
例如下面兩棵樹要合併：
最後得到如下的樹：
inline int merge(int a,int b){
if(!a || !b) return a+b; if(rnd[a] < rnd[b]){ rs(a)=merge(rs(a),b); update(a);return a; } else{ ls(b)=merge(a,ls(b)); update(b);return b; } }
find
這裡我的find函數是找到以該點為根的樹的排名為k的數的位置，同樣是去看左子樹的大小。
inline int find(int id,int k){//返回的以id為根的樹的第k個數的位置 while(true){ if(k<=sze[ls(id)]) id=ls(id); else if(k==sze[ls(id)]+1) return id; else k-=sze[ls(id)]+1,id=rs(id); } }
insert
從根節點開始分裂，然後依次合併x樹和該點，再合併y樹。
inline int new_node(int x){ sze[++cnt]=1; val[cnt]=x; rnd[cnt]=rand(); return cnt; } inline void insert(int val){ split(root,val,x,y); root=merge(merge(x,new_node(val)),y); }
delete
在用一棵臨時樹z，先從根節點按val分裂，再從x節點按val-1分裂，最後按順序有依次合併。
inline void delet(int val){ split(root,val,x,z); split(x,val-1,x,y); y=merge(ls(y),rs(y)); root=merge(merge(x,y),z); }
排名詢問
按val-1去分裂，左子樹的大小+1就是排名，別忘了merge回去。
inline void query_rank(int val){ split(root,val-1,x,y);
print(sze[x]+1); root=merge(x,y); }
第k大的數
用find函數就行
找前後驅
同理，還是先split，再merge。
////www.luogu.com.cn/blog/Chanis/fhq-treap #pragma GCC optimize(3) #include<cstdio> #include<iostream> #include<algorithm> #include<cctype> #include<cstdlib> #include<ctime> using namespace std; inline int read(){ int s=0;bool flag=true;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')flag=false;ch=getchar();} while(isdigit(ch)){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();} return flag?s:-s; } inline void write(int x){ if(x<0) x=-x,putchar('-'); if(x>9) write(x/10); putchar(x%10+'0'); } inline void print(int x){write(x);puts("");} const int N=5e5+10; int root,x,y,z,cnt; struct Treap{ int ch[N][2],val[N],rnd[N],sze[N]; #define ls(id) ch[id][0] #define rs(id) ch[id][1] inline void update(int x){sze[x]=sze[ch[x][0]]+sze[ch[x][1]]+1;} inline void split(int id,int k,int &x,int &y){ if(!id){x=y=0;return ;} if(val[id]<=k){x=id;split(rs(id),k,rs(id),y);} else{y=id;split(ls(id),k,x,ls(id));} update(id); } inline int merge(int a,int b){ if(!a || !b) return a+b; if(rnd[a] < rnd[b]){ rs(a)=merge(rs(a),b); update(a);return a; } else{ ls(b)=merge(a,ls(b)); update(b);return b; } } inline int new_node(int x){ sze[++cnt]=1; val[cnt]=x; rnd[cnt]=rand(); return cnt; } inline int find(int id,int k){//返回的以id為根的樹的第k個數的位置 while(true){ if(k<=sze[ls(id)]) id=ls(id); else if(k==sze[ls(id)]+1) return id; else k-=sze[ls(id)]+1,id=rs(id); } } inline void insert(int val){ split(root,val,x,y); root=merge(merge(x,new_node(val)),y); } inline void delet(int val){ split(root,val,x,z); split(x,val-1,x,y); y=merge(ls(y),rs(y)); root=merge(merge(x,y),z); } inline void query_rank(int val){ split(root,val-1,x,y); print(sze[x]+1); root=merge(x,y); } inline void query_value(int k){ print(val[find(root,k)]); } inline void query_pre(int value){ split(root,value-1,x,y); print(val[find(x,sze[x])]); root=merge(x,y); } inline void query_suf(int value){ split(root,value,x,y); print(val[find(y,1)]); root=merge(x,y); } }Tree; signed main(void){ srand((unsigned)time(NULL)); int T=read(); while(T--){ int opt=read(),t=read(); switch(opt){ case 1: Tree.insert(t);break; case 2: Tree.delet(t);break; case 3: Tree.query_rank(t);break; case 4: Tree.query_value(t);break; case 5: Tree.query_pre(t);break; case 6: Tree.query_suf(t);break; } } return 0; }
5*.關於fhq-treap的可持久化
還沒有學懂，後面再更新。
