一定要放在最前面的：
超詳細
同上
+1
\(Splay\) 一個支持功能和 \(Treap\) 差不多的東西，只是更高級（有六種旋轉操作）
既然是一種平衡樹，那就具有 \(BST\) 性質
模板
\(Update\)
void update(int p){
tr[p].size=tr[tr[p].son[0]].size+tr[tr[p].son[1]].size+tr[p].cnt;
//更新子樹大小用于查詢排名 ↑
}
\(Rotate\)
基本旋轉操作
\(Treap\) 左旋和右旋操作的合并操作：
-
X變到原來Y的位置
-
Y變成了 X原來在Y的 相對的那個兒子
-
Y的非X的兒子不變 X的 X原來在Y的 那個兒子不變
-
X的 X原來在Y的 相對的 那個兒子 變成了 Y原來是X的那個兒子
void rotate(int x){
int y=tr[x].fa,z=tr[y].fa,k=(tr[y].son[1]==x);
//y是x的父親，z是爺爺
//k用于判斷x是y的左兒子還是右兒子;0:左，1:右
tr[z].son[tr[z].son[1]==y]=x;
tr[x].fa=z;
//x頂替y的位置 ↑
tr[y].son[k]=tr[x].son[k^1];
tr[tr[x].son[k^1]].fa=y;
//改變x的另一個兒子 ↑
tr[x].son[k^1]=y;
tr[y].fa=x;
//更改x，y的關系 ↑
update(y),update(x);//記得修改
}
\(Spaly\)
比 \(Treap\) 多出的旋轉操作
單純對 \(X\) 旋轉兩次后仍然有一條鏈的存在，還是可能會被卡
所以才有了 \(Splay\) 操作
兩種情況：
-
X和Y分別是Y和Z的同一個兒子
-
X和Y分別是Y和Z不同的兒子
第一種情況：先轉Y再轉X
第二種情況：轉兩次X
另外兩種情況：
不存在Z，即Y是樹的根，只需要對X進行一次旋轉即可
void splay(int x,int goal){//將x轉為goal的兒子
while(tr[x].fa!=goal){
int y=tr[x].fa,z=tr[y].fa;
if(z!=goal)//y已經是目標節點的兒子，只需要轉一次
((tr[z].son[0]==y)^(tr[y].son[0]==x))?rotate(x):rotate(y);
//在同一側轉y，否則轉x
rotate(x);//最后轉的都是x
}
if(goal==0) root=x;//0是根的父親，記得換根
}
\(Find\)
查找后根就是要找的節點
void fi(int x){
int u=root;
if(!u) return;//樹為空
while(tr[u].son[x>tr[u].val] && x!=tr[u].val)
u=tr[u].son[x>tr[u].val];//進入相應節點
splay(u,0);//此時u為查找值的編號，并旋轉到根
}
\(Insert\)
和 \(Treap\) 的差不多
void insert(int x){
int fa=0,u=root;//fa是要插入節點的父節點
while(u && x!=tr[u].val){
fa=u;
u=tr[u].son[x>tr[u].val];
}
if(u) tr[u].cnt++;//存在直接累加值就好了
else{
u=++tot;
if(fa) tr[fa].son[x>tr[fa].val]=u;
tr[u].son[1]=tr[u].son[0]=0;
tr[u].fa=fa,tr[u].val=x,tr[u].cnt=1,tr[u].size=1;
}
splay(u,0);
//一定要轉到根保證平衡，前面改了子樹大小所以借此update
}
前驅&后繼
int nxt(int x,bool k){//1為后繼,0為前驅
fi(x);
int u=root;
if(tr[u].val>x && k) return u;
if(tr[u].val<x && !k) return u;
u=tr[u].son[k];
while(tr[u].son[k^1]) u=tr[u].son[k^1];
return u;
}
\(Remove\)
void remove(int x){
int la=nxt(x,0),nex=nxt(x,1);
splay(la,0),splay(nex,la);
//將前驅旋轉到根節點，后繼旋轉到根節點下面
int del=tr[nex].son[0];
if(tr[del].cnt>1){
tr[del].cnt--;
splay(del,0);//修改子樹大小
}
else tr[nex].son[0]=0;//直接刪
}
找第 \(k\) 大
比較重要，還是附個代碼吧
int kth(int x){//查第k大
int u=root;
if(tr[u].size<x) return 0;
while(1){
int y=tr[u].son[0];
if(x>tr[y].size+tr[u].cnt){
x-=tr[y].size+tr[u].cnt;
u=tr[u].son[1];
}
else{
if(tr[y].size>=x) u=y;
else return u;
}
}
}
\(Code\)
#include<bits/stdc++.h>
using namespace std;
#define INF 20000000
const int N=1e5+5;
struct splay_tree{
int fa,son[2],cnt,val,size;
}tr[N];
int root,tot;
inline void update(int p){
tr[p].size=tr[tr[p].son[0]].size+tr[tr[p].son[1]].size+tr[p].cnt;
}
inline void rotate(int x){
int y=tr[x].fa,z=tr[y].fa,k=(tr[y].son[1]==x);
tr[z].son[tr[z].son[1]==y]=x;
tr[x].fa=z;
tr[y].son[k]=tr[x].son[k^1];
tr[tr[x].son[k^1]].fa=y;
tr[x].son[k^1]=y;
tr[y].fa=x;
update(y),update(x);
}
inline void splay(int x,int goal){
while(tr[x].fa!=goal){
int y=tr[x].fa,z=tr[y].fa;
if(z!=goal)
((tr[z].son[0]==y)^(tr[y].son[0]==x))?rotate(x):rotate(y);
rotate(x);
}
if(goal==0) root=x;
}
inline void fi(int x){
int u=root;
if(!u) return;
while(tr[u].son[x>tr[u].val] && x!=tr[u].val)
u=tr[u].son[x>tr[u].val];
splay(u,0);
}
inline void insert(int x){
int fa=0,u=root;
while(u && x!=tr[u].val){
fa=u;
u=tr[u].son[x>tr[u].val];
}
if(u) tr[u].cnt++;
else{
u=++tot;
if(fa) tr[fa].son[x>tr[fa].val]=u;
tr[u].son[1]=tr[u].son[0]=0;
tr[u].fa=fa,tr[u].val=x,tr[u].cnt=1,tr[u].size=1;
}
splay(u,0);
}
inline int nxt(int x,bool k){
fi(x);
int u=root;
if(tr[u].val>x && k) return u;
if(tr[u].val<x && !k) return u;
u=tr[u].son[k];
while(tr[u].son[k^1]) u=tr[u].son[k^1];
return u;
}
inline void remove(int x){
int la=nxt(x,0),nex=nxt(x,1);
splay(la,0),splay(nex,la);
int del=tr[nex].son[0];
if(tr[del].cnt>1){
tr[del].cnt--;
splay(del,0);
}
else tr[nex].son[0]=0;
}
inline int rk(int p,int x){
if(!p) return 0;
if(x==tr[p].val)
return tr[tr[p].son[0]].size+1;
if(x>tr[p].val)
return rk(tr[p].son[1],x)+tr[tr[p].son[0]].size+tr[p].cnt;
return rk(tr[p].son[0],x);
}
inline int kth(int x){
int u=root;
if(tr[u].size<x) return 0;
while(1){
int y=tr[u].son[0];
if(x>tr[y].size+tr[u].cnt){
x-=tr[y].size+tr[u].cnt;
u=tr[u].son[1];
}
else{
if(tr[y].size>=x) u=y;
else return u;
}
}
}
int main(){
int n;
cin>>n;
insert(-INF),insert(INF);
while(n--){
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1) insert(x);
if(opt==2) remove(x);
if(opt==3) cout<<rk(root,x)-1<<endl;
if(opt==4) cout<<tr[kth(x+1)].val<<endl;
if(opt==5) cout<<tr[nxt(x,0)].val<<endl;
if(opt==6) cout<<tr[nxt(x,1)].val<<endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423937.html
標籤：其他