【数据结构】Splay详解

大家好，欢迎来到IT知识分享网。

引入

1. 空树是二叉搜索树。
2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
4. 二叉搜索树的左右子树均为二叉搜索树。

二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 $n$ 个结点的二叉搜索树中，这些操作的最优时间复杂度为 $O(\log n)$

如图就是一颗典型的 BST(二叉查找树)

可是我们发现，如果树退化成一条链，那么时间复杂度将退化为 $O(n)$，这是我们不能接受的，于是平衡树孕育而生，其核心就是维护一颗相对平衡的 BST。
本文将介绍Splay，虽然它并不能保证树一直是”平衡”的，但对于Splay的一系列操作，我们可以证明其每步操作的平摊复杂度都是 $O(\log n)$。所以从某种意义上说，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$ 为父节点的左儿子还是右儿子，pushup为由下往上更新。

splay操作

这个操作可以说是Splay的核心操作之一，可以理解为把某个点通过旋转操作旋转到根节点。
那么如何将一个节点旋转到根节点呢？
首先有 $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$，让splay把 $x$ 旋转到 $y$ 的儿子上。(当 $y=0$ 时将 $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排名

 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$ 的后继旋转到根节点的右子树上，这样根节点的右子树的左儿子即为目标节点，直接断开联系即为删除。
参考代码：

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; } 

模板

题目概述：

参考代码：

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时间复杂度分析

进阶操作

截取区间

Splay还可应用到序列操作中，具体而言，如果我们需要对区间 $[l,r]$进行操作，我们只需要先将 $l-1$ 弄到根节点，再把 $r+1$ 弄到根节点的右儿子上，那么它的左子树就是区间 $[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"; } 

一些好题

P2042
P4008
P6707

参考文献

1. OI-WIKI
2. 伸展树的基本操作和应用——杨思雨
3. 各位大佬的博客和题解