[数据结构] Splay
与 Treap 相比,并没有堆性质的限制,而是通过其灵活变换维持复杂度。
是均摊 \(\text O(logn)\) 的数据结构。
本来 Zhang_RQ 早就讲了,今天才学会
概念类
需要维护的 基本 东西有:
左右儿子,父亲,权值,一般会维护 \(sz\) 和 \(cnt\),便于进行二分操作。
基本操作
特有操作---rotate and splay
所谓 \(rotate\) 操作,就是把一个点 \(x\) 转到父亲上,分为左旋和右旋。
也就是四句话:
让父亲变成它的儿子,让祖父变成它的父亲,保留一侧的儿子,让另一侧的儿子变成它父亲的一侧儿子。
其中一侧表示 \(x\) 是左儿子还是右儿子,是一种相对关系。
对于 splay ,可以简单理解为多个 rotate 使得 \(x\) 处于终点位置。
注意:儿子和父亲单侧的时候要先转父亲再转儿子,注意最后 pushup 的顺序。
void rotate(int x){
int y=fa[x],z=fa[y];
bool rsx=rson(x),rsy=rson(y);
if(z)ch[z][rsy]=x;
else rt=x;
ch[y][rsx]=ch[x][!rsx];ch[x][!rsx]=y;
fa[y]=x;fa[x]=z;fa[ch[y][rsx]]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k){//把 x 转到 k
int root=fa[k];
while(fa[x]!=root){
int y=fa[x],z=fa[y];
if(z==root)rotate(x);
else rotate(rson(x)==rson(y)?y:x),rotate(x);
}
k=x;//传引用给树根
}
插入操作
int find(int x){//找到 权值x 所在结点编号
int nw=rt;
while(nw){
if(val[nw]==x){splay(nw,rt);return nw;}//注意最后要 splay
if(val[nw]<x)nw=ch[nw][1];
else nw=ch[nw][0];
}
return 0;
}
void insert(int x){
if(!rt)return rt=nd(x,0),void();//特判空树
int nw=rt;
while(nw){
if(val[nw]==x){//先判是否已经存在
sz[nw]++;cnt[nw]++;splay(nw,rt);return ;
}
bool fl=val[nw]<x;//巧妙的写法
if(!ch[nw][fl]){
ch[nw][fl]=nd(x,nw);splay(ch[nw][fl],rt);
return ;
}
else nw=ch[nw][fl];
}
}
删除结点操作
注意不要漏情况。
void del(int x){
int nw=find(x);//nw已经是根
if(cnt[nw]>1){cnt[nw]--;sz[nw]--;return;}
if(!ch[nw][0] && !ch[nw][1]){rt=0;return ;}
if(!ch[nw][0]){rt=ch[nw][1];fa[ch[nw][1]]=0;return ;}
if(!ch[nw][1]){rt=ch[nw][0];fa[ch[nw][0]]=0;return ;}
int y=ch[nw][0];
while(ch[y][1])y=ch[y][1];splay(y,ch[nw][0]);
ch[ch[nw][0]][1]=ch[nw][1];fa[ch[nw][1]]=ch[nw][0];
fa[ch[nw][0]]=0;rt=ch[nw][0];
pushup(rt);
}
其他平衡树的操作
int Kth(int k){
int nw=rt;
while(k){
int num=cnt[nw]+sz[ch[nw][0]];
if(k<=num && k>sz[ch[nw][0]])return val[nw];
if(k<num)nw=ch[nw][0];
else k-=num,nw=ch[nw][1];
}
return 0;
}
const int INF = 0x3f3f3f3f;
int pre(int x){
int nw=rt,ans=-INF;
while(nw){
if(val[nw]<x)ans=max(ans,val[nw]),nw=ch[nw][1];
else nw=ch[nw][0];
}
return ans;
}
int suc(int x){
int nw=rt,ans=INF;
while(nw){
if(val[nw]>x)ans=min(ans,val[nw]),nw=ch[nw][0];
else nw=ch[nw][1];
}
return ans;
}
int Rank(int x){
int nw=find(x);
return sz[ch[nw][0]]+1;
}
总代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template <typename T>
inline T read(){
T x=0;char ch=getchar();bool fl=false;
while(!isdigit(ch)){if(ch=='-')fl=true;ch=getchar();}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+(ch^48);ch=getchar();
}
return fl?-x:x;
}
const int maxn = 1e5 + 10;
int val[maxn],ch[maxn][2],fa[maxn],sz[maxn],cnt[maxn];
int rt;
inline void pushup(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];return ;
}
inline bool rson(int x){return ch[fa[x]][1]==x;}
void rotate(int x){
int y=fa[x],z=fa[y];
bool rsx=rson(x),rsy=rson(y);
if(z)ch[z][rsy]=x;
else rt=x;
ch[y][rsx]=ch[x][!rsx];ch[x][!rsx]=y;
fa[y]=x;fa[x]=z;fa[ch[y][rsx]]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k){
int root=fa[k];
while(fa[x]!=root){
int y=fa[x],z=fa[y];
if(z==root)rotate(x);
else rotate(rson(x)==rson(y)?y:x),rotate(x);
}
k=x;//传引用给树根
}
int find(int x){
int nw=rt;
while(nw){
if(val[nw]==x){splay(nw,rt);return nw;}
if(val[nw]<x)nw=ch[nw][1];
else nw=ch[nw][0];
}
return 0;
}
int tot;
inline int nd(int x,int f){
val[++tot]=x;fa[tot]=f;
sz[tot]=cnt[tot]=1;
return tot;
}
void insert(int x){
if(!rt)return rt=nd(x,0),void();
int nw=rt;
while(nw){
if(val[nw]==x){
sz[nw]++;cnt[nw]++;splay(nw,rt);return ;
}
bool fl=val[nw]<x;
if(!ch[nw][fl]){
ch[nw][fl]=nd(x,nw);splay(ch[nw][fl],rt);
return ;
}
else nw=ch[nw][fl];
}
}
void del(int x){
int nw=find(x);
if(cnt[nw]>1){cnt[nw]--;sz[nw]--;return;}//nw已经是根
if(!ch[nw][0] && !ch[nw][1]){rt=0;return ;}
if(!ch[nw][0]){rt=ch[nw][1];fa[ch[nw][1]]=0;return ;}
if(!ch[nw][1]){rt=ch[nw][0];fa[ch[nw][0]]=0;return ;}
int y=ch[nw][0];
while(ch[y][1])y=ch[y][1];splay(y,ch[nw][0]);
ch[ch[nw][0]][1]=ch[nw][1];fa[ch[nw][1]]=ch[nw][0];
fa[ch[nw][0]]=0;rt=ch[nw][0];
pushup(rt);
}
int Kth(int k){
int nw=rt;
while(k){
int num=cnt[nw]+sz[ch[nw][0]];
if(k<=num && k>sz[ch[nw][0]])return val[nw];
if(k<num)nw=ch[nw][0];
else k-=num,nw=ch[nw][1];
}
return 0;
}
const int INF = 0x3f3f3f3f;
int pre(int x){
int nw=rt,ans=-INF;
while(nw){
if(val[nw]<x)ans=max(ans,val[nw]),nw=ch[nw][1];
else nw=ch[nw][0];
}
return ans;
}
int suc(int x){
int nw=rt,ans=INF;
while(nw){
if(val[nw]>x)ans=min(ans,val[nw]),nw=ch[nw][0];
else nw=ch[nw][1];
}
return ans;
}
int Rank(int x){
int nw=find(x);
cerr<<"nw:"<<nw<<endl;//
return sz[ch[nw][0]]+1;
}
#define read() read<int>()
int main(){
int n=read();
while(n--){
int op=read(),x=read();
if(op==1)insert(x);
if(op==2)del(x);
if(op==3)printf("%d\n",Rank(x));
if(op==4)printf("%d\n",Kth(x));
if(op==5)printf("%d\n",pre(x));
if(op==6)printf("%d\n",suc(x));
}
return 0;
}