Splay
引入
首先我们要知道一个东西叫二叉搜索树。
其定义如下：
- 空树是二叉搜索树。
- 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
- 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
- 二叉搜索树的左右子树均为二叉搜索树。
二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 n n n 个结点的二叉搜索树中，这些操作的最优时间复杂度为 O ( log n ) O(\log n) O(logn)
如图就是一颗典型的 BST(二叉查找树)
可是我们发现，如果树退化成一条链，那么时间复杂度将退化为 O ( n ) O(n) O(n)，这是我们不能接受的，于是平衡树孕育而生，其核心就是维护一颗相对平衡的 BST。
本文将介绍Splay，虽然它并不能保证树一直是"平衡"的，但对于Splay的一系列操作，我们可以证明其每步操作的平摊复杂度都是 O ( log n ) O(\log n) O(logn)。所以从某种意义上说，Splay也是一种平衡的二叉查找树。
Splay
旋转操作
下面参考 OI-WIKI的介绍。
注意，左右旋指的是向左或右旋转。
左旋为ZAG，右旋为ZIG
以下是一次标准旋转操作：
我们可以知道，旋转流程如下：
于是我们便可以写出 ZIG和ZAG函数，参考下列代码：
不过有时候为了方便表示，我们可以把两个旋转操作合并起来。
就成了 rotate(旋转)函数，以下是参考代码：
void rotate(int x){
int y=fa[x],z=fa[y],id=son_(x);
ch[y][id]=ch[x][id^1];
if(ch[x][id^1])
fa[ch[x][id^1]]=y;
ch[x][id^1]=y;
fa[y]=x;
fa[x]=z;
if(z)
ch[z][y==ch[z][1]]=x;
pushup(y);
pushup(x);
}
其中 son_( x x x)是判断 x x x 为父节点的左儿子还是右儿子，pushup为由下往上更新。
splay操作
这个操作可以说是Splay的核心操作之一，可以理解为把某个点通过旋转操作旋转到根节点。
那么如何将一个节点旋转到根节点呢？
首先有 6 6 6 种基本情况，见下图：
那么我们只需要不断重复执行旋转操作，即可旋转到根节点。
以下是参考代码：
void splay(int x) {
for (int f = fa[x]; f = fa[x], f; rotate(x))
if (fa[f])
rotate(get(x) == get(f) ? f : x);
rt = x;
}
一些进阶：
由于后面某些操作需要用到，所以我们对splay函数进行一些修改。
具体而言，我们引入一个参数 y y y，让splay把 x x x 旋转到 y y y 的儿子上。(当 y = 0 y=0 y=0 时将 x x x 旋转到根节点)
其实也没什么改动，见参考代码：
void splay(int x,int y){
while(fa[x]!=y){
if(fa[fa[x]]!=y){
if(son_(fa[x])==son_(x))
rotate(fa[x]);
else
rotate(x);
}
rotate(x);
}
if(!y)
rt=x;
}
插入操作
解释一下：
二叉树的性质使得插入操作变得非常简易，具体而言，只要值比当前节点大，就往右子树找，小就往左子树找，一样就让计数器+1，如果找不到匹配的值就直接新建一个节点。
参考代码：
void add(int k){
if(!rt){
rt=++idx;
cnt[rt]++,val[rt]=k;
pushup(rt);
return ;
}
int x=rt,y=0;
while(1){
if(val[x]==k){
cnt[x]++;
pushup(x),pushup(y);
splay(x,0);
break;
}
y=x;
x=ch[x][val[x]<k];
if(!x){
cnt[++idx]++,val[idx]=k;
fa[idx]=y;
ch[y][val[y]<k]=idx;
pushup(idx);
pushup(y);
splay(idx,0);
break;
}
}
}
查询x排名
这个跟插入差不多，从根节点不断往下找，每次向右子树找时加上左子树的size+1，因为左子树和根的值一定比查询值小(BST的性质)。
具体详见代码：
int x_rank(int k){
int rk=0,x=rt;
while(1){
if(k<val[x])
x=ch[x][0];
else{
rk+=sz[ch[x][0]];
if(!x)
return rk+1;
if(k==val[x]){
splay(x,0);
return rk+1;
}
rk+=cnt[x];
x=ch[x][1];
}
}
}
查询排名为x
这个跟上面两个操作都差不多，不断往下找就行了。
看着代码，画画图也就能理解了。
int kth(int k){
int x=rt;
while(1){
if(ch[x][0]&&k<=sz[ch[x][0]])
x=ch[x][0];
else{
k-=sz[ch[x][0]];
if(k<=cnt[x]){
splay(x,0);
return val[x];
}
k-=cnt[x];
x=ch[x][1];
}
}
}
删除操作
这个就感性理解一下。
参考代码：
void del(int k){
x_rank(k);
int x=rt,y=0;
if(cnt[rt]>1)
cnt[rt]--,pushup(rt);
else if(!ch[rt][0]&&!ch[rt][1])
clean(rt),rt=0;
else if(!ch[rt][0]){
rt=ch[rt][1];
fa[rt]=0;
clean(x);
}
else if(!ch[rt][1]){
rt=ch[rt][0];
fa[rt]=0;
clean(x);
}
else{
pre();
fa[ch[x][1]]=rt;
ch[rt][1]=ch[x][1];
clean(x),pushup(rt);
}
}
或者还有一种方式，我们把 x x x 的前驱旋转到根节点，再把 x x x 的后继旋转到根节点的右子树上，这样根节点的右子树的左儿子即为目标节点，直接断开联系即为删除。
参考代码：
void del(int x){
int l=kth(x-1),r=kth(r+1);
splay(l,0),splay(r,l);
fa[ch[r][0]]=0,ch[r][0]=0;
pushup(r);
pushup(l);
}
查询前驱/后继
这个可以先将这个节点插入，此时它在根节点，那么前驱就是它左子树中最右的点，后继就是它右子树中最左的点。
查询完我们在删除这个点即可。
参考代码：
int pre(){
int z=ch[rt][0];
while(ch[z][1])
z=ch[z][1];
splay(z,0);
return z;
}
int nxt(){
int z=ch[rt][1];
while(ch[z][0])
z=ch[z][0];
splay(z,0);
return z;
}
模板
综合上述操作，我们即可A掉洛谷模版题。
P3369 【模板】普通平衡树
题目概述：
参考代码：
struct Tr_splay{
int fa[N],ch[N][2],sz[N],val[N],cnt[N];
void pushup(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
void clean(int x){
fa[x]=sz[x]=cnt[x]=val[x]=ch[x][0]=ch[x][1]=0;
}
bool son_(int x){
return x==ch[fa[x]][1];
}
void rotate(int x){
int y=fa[x],z=fa[y],id=son_(x);
ch[y][id]=ch[x][id^1];
if(ch[x][id^1])
fa[ch[x][id^1]]=y;
ch[x][id^1]=y;
fa[y]=x;
fa[x]=z;
if(z)
ch[z][y==ch[z][1]]=x;
pushup(y);
pushup(x);
}
void splay(int x,int y){
while(fa[x]!=y){
if(fa[fa[x]]!=y){
if(son_(fa[x])==son_(x))
rotate(fa[x]);
else
rotate(x);
}
rotate(x);
}
if(!y)
rt=x;
}
int pre(){
int z=ch[rt][0];
while(ch[z][1])
z=ch[z][1];
splay(z,0);
return z;
}
int nxt(){
int z=ch[rt][1];
while(ch[z][0])
z=ch[z][0];
splay(z,0);
return z;
}
void add(int k){
if(!rt){
rt=++idx;
cnt[rt]++,val[rt]=k;
pushup(rt);
return ;
}
int x=rt,y=0;
while(1){
if(val[x]==k){
cnt[x]++;
pushup(x),pushup(y);
splay(x,0);
break;
}
y=x;
x=ch[x][val[x]<k];
if(!x){
cnt[++idx]++,val[idx]=k;
fa[idx]=y;
ch[y][val[y]<k]=idx;
pushup(idx);
pushup(y);
splay(idx,0);
break;
}
}
}
int x_rank(int k){
int rk=0,x=rt;
while(1){
if(k<val[x])
x=ch[x][0];
else{
rk+=sz[ch[x][0]];
if(!x)
return rk+1;
if(k==val[x]){
splay(x,0);
return rk+1;
}
rk+=cnt[x];
x=ch[x][1];
}
}
}
int kth(int k){
int x=rt;
while(1){
if(ch[x][0]&&k<=sz[ch[x][0]])
x=ch[x][0];
else{
k-=sz[ch[x][0]];
if(k<=cnt[x]){
splay(x,0);
return val[x];
}
k-=cnt[x];
x=ch[x][1];
}
}
}
void del(int k){
x_rank(k);
int x=rt,y=0;
if(cnt[rt]>1)
cnt[rt]--,pushup(rt);
else if(!ch[rt][0]&&!ch[rt][1])
clean(rt),rt=0;
else if(!ch[rt][0]){
rt=ch[rt][1];
fa[rt]=0;
clean(x);
}
else if(!ch[rt][1]){
rt=ch[rt][0];
fa[rt]=0;
clean(x);
}
else{
pre();
fa[ch[x][1]]=rt;
ch[rt][1]=ch[x][1];
clean(x),pushup(rt);
}
}
}tree;
signed main(){
IOS;
cin>>m;
while(m--){
int x,y;
cin>>x>>y;
if(x==1)tree.add(y);
if(x==2)tree.del(y);
if(x==3)tree.add(y),cout<<tree.x_rank(y)<<"\n",tree.del(y);
if(x==4)cout<<tree.kth(y)<<"\n";
if(x==5)tree.add(y),cout<<tree.val[tree.pre()]<<"\n",tree.del(y);
if(x==6)tree.add(y),cout<<tree.val[tree.nxt()]<<"\n",tree.del(y);
}
return 0;
}
Splay时间复杂度分析
这个蒟蒻不会，但可以参考 OI-WIKI的证明：
证明
进阶操作
截取区间
Splay还可应用到序列操作中，具体而言，如果我们需要对区间 [ l , r ] [l,r] [l,r]进行操作，我们只需要先将 l − 1 l-1 l−1 弄到根节点，再把 r + 1 r+1 r+1 弄到根节点的右儿子上，那么它的左子树就是区间 [ l , r ] [l,r] [l,r]了。
参考代码：
int split(int l,int r){
l=kth(l-1),r=kth(r+1);
splay(l,0);
splay(r,l);
return ch[r][0];
}
//返回区间[l,r]对应的子树的根节点
区间加，区间赋值，区间查询，区间最值
这个类似线段树，我们相应的维护标记，并写好pushdown即可。
区间加参考：
void pushadd(int x,int k){
val[x]+=k;
sum[x]+=k*sz[x];
add[x]+=k;
}
void modify1(int l,int r,int k){
int _=split(l,r);
pushadd(_,0,k);
pushup(r);
pushup(l);
}
区间赋值参考：
void pushcov(int x,int k){
val[x]=k;
sum[x]=sz[x]*k;
add[x]=0;
cov[x]=1;
}
void modify(int l,int r,int k){
int _=split(l,r);
pushcov(_,k);
pushup(r);
pushup(l);
}
区间查询参考：
void ask_sum(int l,int r){
int _=split(l,r);
cout<<sum[_]<<"\n";
}
区间翻转
这个呢我们还是搞一个懒标记然后下传，注意各个标记之间的先后顺序。
参考代码：
void change(int x){
swap(ch[x][0],ch[x][1]);
lazy[x]^=1;
}
void reverse(int l,int r){
l=kth(l),r=kth(r+2);
splay(l,0);
splay(r,l);
change(ch[ch[l][1]][0]);
}
原序列整体插入
有时候题目会直接给我们一个初始序列，一个个插入过于麻烦，于是我们可以类似线段树直接建树。
参考代码：
int create(int k){
int x=top?rb[top--]:++ID;
ch[x][0]=ch[x][1]=fa[x]=rev[x]=cov[x]=0;
sz[x]=1;
val[x]=mx[x]=sum[x]=k;
lx[x]=rx[x]=max(0ll,k);
return x;
}
一些毒瘤题卡空间，这样回收可以节省空间。
int build(int l,int r,int *a){
if(l>r)
return 0;
if(l==r)
return create(a[l]);
int mid=(l+r)>>1,x=create(a[mid]);
ch[x][0]=build(l,mid-1,a);
ch[x][1]=build(mid+1,r,a);
fa[ch[x][0]]=fa[ch[x][1]]=x;
pushup(x);
return x;
}
rt=build(1,n,a);
指定位置插入
这个可以参考查询排名为x的操作。
能看到这里说明你已经是大佬了，看着代码画画图即可理解吧。
void add(int pos,int k){
kth(pos);
pushdown(rt);
fa[ch[rt][0]]=++ID,ch[ID][0]=ch[rt][0];
ch[rt][0]=ID,fa[ID]=rt;
sz[ID]=1;
val[ID]=sum[ID]=k;
pushup(ID);
pushup(rt);
}
整体插入末尾
这个也比较抽象，类似于建一棵新的splay，然后合并。
void insert(int pos,int len,int *a){
int _=build(1,len,a);
int y=kth(pos),x=kth(pos+1);
splay(y,0);
splay(x,y);
ch[x][0]=_,fa[_]=x;
pushup(x);
pushup(y);
}
区间最大子段和
参考线段树，我们维护3个标记：
lx:从左起的最大子段和
mx:整个区间的最大子段和
rx:从右起的最大子段和
参考代码：(由于同时维护区间赋值和区间翻转，代码比较抽象)
void pushup(int x){
sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
lx[x]=max(lx[ch[x][0]],sum[ch[x][0]]+val[x]+lx[ch[x][1]]);
rx[x]=max(rx[ch[x][1]],sum[ch[x][1]]+val[x]+rx[ch[x][0]]);
mx[x]=max(max(mx[ch[x][0]],mx[ch[x][1]]),rx[ch[x][0]]+val[x]+lx[ch[x][1]]);
}
void pushdown(int x){
if(cov[x]){
if(ch[x][0])val[ch[x][0]]=val[x],cov[ch[x][0]]=1,sum[ch[x][0]]=val[x]*sz[ch[x][0]];
if(ch[x][1])val[ch[x][1]]=val[x],cov[ch[x][1]]=1,sum[ch[x][1]]=val[x]*sz[ch[x][1]];
if(val[x]>0){
if(ch[x][0])lx[ch[x][0]]=rx[ch[x][0]]=mx[ch[x][0]]=sum[ch[x][0]];
if(ch[x][1])lx[ch[x][1]]=rx[ch[x][1]]=mx[ch[x][1]]=sum[ch[x][1]];
}
else{
if(ch[x][0])lx[ch[x][0]]=rx[ch[x][0]]=0,mx[ch[x][0]]=val[x];
if(ch[x][1])lx[ch[x][1]]=rx[ch[x][1]]=0,mx[ch[x][1]]=val[x];
}
cov[x]=0;
}
if(rev[x]){
if(ch[x][0])
rev[ch[x][0]]^=1,swap(ch[ch[x][0]][0],ch[ch[x][0]][1]),swap(lx[ch[x][0]],rx[ch[x][0]]);
if(ch[x][1])
rev[ch[x][1]]^=1,swap(ch[ch[x][1]][0],ch[ch[x][1]][1]),swap(lx[ch[x][1]],rx[ch[x][1]]);
rev[x]=0;
}
}
void ask_max_sum(){
cout<<mx[rt]<<"\n";
}
一些好题
参考文献
- OI-WIKI
- 伸展树的基本操作和应用——杨思雨
- 各位大佬的博客和题解
