Splay入门详解

最近新学了Splay,似乎并没有想象中的那么难……之前其实也学过Splay,只是那时看到LG写的6个旋转版本的Splay……就不想写了……这次发现……其实旋转两个函数就可以了,总共十来行……嗯这篇文章我要详解一下。

Splay操作详解

从二叉查找树到Splay

二叉查找树(BST)相信都会吧……其性质就是保证了这棵树的中序遍历是有序的。这样我们就能进行插入,删除,单点修改点权,查找第k大或第k小等基本操作。所有的操作在随机数据下,都能做到$O(logn)$的时间复杂度。
但是BST是有缺陷的。比如说,丧心病狂的出题人把数据从小到大输进来,那么,BST建出的这棵树就退化为了一条链,于是所有的操作就变成$O(n)$的了……这当然是我们不愿意看到的,于是就要用Splay进行平衡。

Splay

Splay的平衡主要基于一个操作,即Splay(伸展操作)。这个操作就是把需要进行操作的点旋转到根节点,便于进行一些维护。但是……旋转操作该怎么搞呢?

Rotate

旋转操作是对Splay进行平衡的主要操作,通过这个操作,可以使Splay的深度变浅,使得复杂度达到一个比较理想的状态。
但是,旋转是不能破坏BST的性质的,即中序遍历的有序性。所以不能随便旋转……
Rotate操作,如果要细分的话,分为以下三大类:(注:Zig为右旋,Zag为左旋)

Zig/Zag

如果我要旋转的节点是根节点的儿子了,那么只需做一次旋转就好了。比如对于这样一张图:

比如我要将$x$旋转到根节点,只需做一下旋转,变成下图的样子,就可以了。

ZigZig/ZagZag

如果这个点的父亲与父亲的父亲三点共线,如果只使用上图的两次单旋,你会发现,如果这棵树是一条链的话,做了两次旋转后,仍然是一条链,对复杂度并没有优化作用,于是我们要进行双旋。
具体来说,就是先将父节点向上旋转一次,再将要旋转的节点向上旋转一次:
比如对于这样一张图:

旋转后就变成了:

ZigZag/ZagZig

如果以上两种情况都不属于的话,我们只需对要旋转的节点向上做两次旋转,就可以了。
比如说对于这样一张图:

旋转后变为:

Rotate&Splay操作总结

不难发现,以上的所有旋转,其实都是基于第一个操作,即Zig/Zag的。所以我们在Splay函数中,不断的进行以上三种旋转之一,直到该节点旋转到根节点即可。当然所有的旋转也并没有破坏它的中序遍历。代码实现上并不难做。先上Rotate函数。

1
2
3
4
5
6
7
inline void Rotate(int x,bool f){
int y=fa[x],u=ch[x][f^1];
if(fa[y])ch[fa[y]][ch[fa[y]][1] == y]=x;
fa[x]=fa[y];
ch[fa[y]=x][f^1]=y;
ch[fa[u]=y][f]=u;
}

解释一下这个代码。f表示其是左旋还是右旋,ch[x][0/1]分别记录$x$节点的左右儿子。Rotate函数实现的仅仅是一次旋转。
再来Splay函数:

1
2
3
4
5
6
7
8
9
10
inline void Splay(int x,int pos){
int y,z;
for(y=fa[x],z=fa[y];y!=pos;z=fa[y=fa[x]]){
bool f1=(ch[y][1]==x),f2=(ch[z][1]==y);
if(z==pos)Rotate(x,f1);
else if(f1^f2)Rotate(x,f1),Rotate(x,f2);
else Rotate(y,f2),Rotate(x,f1);
}
if(pos==0)rt=x;
}

再来解释一下,pos指的是$x$号节点要旋转到$pos$节点的子节点。如果要旋到根,pos=0。最后还要根新一下根节点的编号。
关于Splay与Rotate为何能使得树变得平衡……这个我也不知道……

Insert

Insert函数实现的是插入一个节点。方法并不难。对于第一个节点,把它设为根就好。否则,则从根出发,根据节点的权值往左或往右走,最后接到一个节点之后。接好之后,再将这个节点Splay到根。
实现起来如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
inline void Insert(int Val){
if(++cnt != 1){
int pos=rt,posfa,f;
while(size[pos]){
posfa=pos;
if(val[pos]>=Val)pos=ch[pos][0],f=0;
else pos=ch[pos][1],f=1;
}
fa[cnt]=posfa;val[cnt]=Val;ch[posfa][f]=cnt;
size[cnt]=1;Splay(cnt,0);
}
else rt=cnt,size[rt]=1,val[cnt]=Val;
}

Delete

Delete函数与BST的删除非常类似。不过还要将要删除的节点先旋转到根以保证随时平衡。

Update

Update函数一般用来更新子树的大小。在不停的旋转操作中,子树大小当然是在不断变化的,于是要不停的维护子树大小。那维护子树大小,有何作用呢?它可以帮助实现一下的一些操作。
实现起来就这样:

1
2
3
inline void Update(int x){
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}

那么……为何这样就是对的呢?因为Splay在旋转的过程中,是从下到上旋转的,因此更新子树大小时,也是从下到上更新的。于是这么写就没有问题了。
注意在每次旋转操作后和整个Splay操作完成后,都要Update一次。

Find

Find函数实现的是查找整个序列的第$k$大或第$k$小。实现起来并不复杂。只需维护一下子树的大小,然后从根节点往下走。
实现起来长这样:

1
2
3
4
5
6
7
8
inline int Find(int x){
int pos=rt;
while(true){
if(x<=size[ch[pos][0]])pos=ch[pos][0];
else if(x==size[ch[pos][0]]+1)return val[pos];
else x-=size[ch[pos][0]]+1,pos=ch[pos][1];
}
}

对于查询一个数的排名,实现十分类似,在此不再赘述。

Query_Pre/Nxt

查询前驱后继。并不复杂。找到该点后,前驱即为其左子树的最右的节点,后继即为其右子树最左的节点。

例题

BZOJ1588 郁闷的出纳员

题意

OIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要从电脑中把他的工资档案删去,同样,每当公司招聘了一位新员工,我就得为他新建一个工资档案。老板经常到我这边来询问工资情况,他并不问具体某位员工的工资情况,而是问现在工资第k多的员工拿多少工资。每当这时,我就不得不对数万个员工进行一次漫长的排序,然后告诉他答案。好了,现在你已经对我的工作了解不少了。正如你猜的那样,我想请你编一个工资统计程序。怎么样,不是很困难吧?
第一行有两个非负整数$n$和$min$。$n$表示下面有多少条命令,$min$表示工资下界。
接下来的$n$行,每行表示一条命令。命令可以是以下四种之一:
| 名称 | 格式 | 作用 |
| :—-: | :—-: | :—–: |
| I命令 | I_k | 新建一个工资档案,初始工资为k。如果某员工的初始工资低于工资下界,他将立刻离开公司。|
| A命令 | A_k | 把每位员工的工资加上k |
| S命令 | S_k | 把每位员工的工资扣除k |
| F命令 | F_k | 查询第k多的工资 |
I命令的条数不超过$100000$
A命令和S命令的总条数不超过$100$
F命令的条数不超过$100000$
每次工资调整的调整量不超过$1000$
新员工的工资不超过$100000$

题解

对于删除,先查询工资下界的前驱,再把它旋转到根的左子树并一起删掉就可以了。
对于加工资,每个点暴力加就可以。
查询第k大,直接照搬上文代码即可。
嗯还挺裸的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const int maxn=1e5+10;
const long double eps=1e-9;
int Min;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
struct Splay_Tree{
int ch[maxn][2],val[maxn],size[maxn],fa[maxn];
int rt,top,cnt;
inline void Update(int x){
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
inline void Rotate(int x,bool f){
int y=fa[x],u=ch[x][f^1];
if(fa[y])ch[fa[y]][ch[fa[y]][1] == y]=x;
fa[x]=fa[y];
ch[fa[y]=x][f^1]=y;
ch[fa[u]=y][f]=u;
Update(y);
}
inline void Splay(int x,int pos){
int y,z;
for(y=fa[x],z=fa[y];y!=pos;z=fa[y=fa[x]]){
bool f1=(ch[y][1]==x),f2=(ch[z][1]==y);
if(z==pos)Rotate(x,f1);
else if(f1^f2)Rotate(x,f1),Rotate(x,f2);
else Rotate(y,f2),Rotate(x,f1);
}
Update(x);
if(pos==0)rt=x;
}
inline void Insert(int Val){
if(++cnt != 1){
int pos=rt,posfa,f;
while(size[pos]){
posfa=pos;
if(val[pos]>=Val)pos=ch[pos][0],f=0;
else pos=ch[pos][1],f=1;
}
fa[cnt]=posfa;val[cnt]=Val;ch[posfa][f]=cnt;
size[cnt]=1;Splay(cnt,0);
}
else rt=cnt,size[rt]=1,val[cnt]=Val;
}
inline int Query(int Val){
int pos=rt,Pre,Nex;
while(size[pos]){
if(val[pos]>Val)Nex=val[pos],pos=ch[pos][0];
else if(val[pos]==Val){
Nex=Pre=Val;
break;
}
else Pre=val[pos],pos=ch[pos][1];
}
return min(abs(Pre-Val),abs(Nex-Val));
}
}Tree;
int main(){
int i,k,n;
#ifndef ONLINE_JUDGE
freopen("BZOJ1588.in","r",stdin);
freopen("BZOJ1588.out","w",stdout);
#endif
n=read();
int sum=0;
Tree.Insert(INF);
Tree.Insert(-INF);
for(i=1;i<=n;i++){
int val=read();
if(i==1)sum+=val;
else sum+=Tree.Query(val);
Tree.Insert(val);
}
printf("%d\n",sum);
return 0;
}

BZOJ1503 文艺平衡树

题意

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1

题解

Splay同样可以解决区间问题。对于区间修改,我们可以这么做。假设要反转的区间为$[l,r]$,我们找到$l-1$和$r+1$两个点。并把$l-1$旋转到根,把$r+1$旋转到根的右子树,那么要反转的区间就是$r+1$的左子树了。我们直接把这个区间打上反转标记。在每次Splay操作前,先把这次Splay路径上的所有点的标记PushDown,并反转子树的两个区间即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const int maxn=1e5+10;
const long double eps=1e-9;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
struct Splay_Tree{
int ch[maxn][2],fa[maxn],val[maxn],size[maxn],Tag[maxn],stack[maxn];
int rt,cnt,top;
inline void Pushdown(int x){
if(Tag[x]){
int l=ch[x][0],r=ch[x][1];
Tag[x]^=1;
Tag[l]^=1,swap(ch[l][0],ch[l][1]);
Tag[r]^=1,swap(ch[r][0],ch[r][1]);
}
}
inline void Update(int x){
size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
inline void Rotate(int x,bool f){
int y=fa[x],u=ch[x][f^1];
if(fa[y])ch[fa[y]][ch[fa[y]][1] == y]=x;
fa[x]=fa[y];
ch[fa[y]=x][f^1]=y;
ch[fa[u]=y][f]=u;
Update(y);
}
inline void Splay(int x,int pos){
top=1;stack[top]=x;
int i;
for(i=x;fa[i]!=pos;i=fa[i])stack[++top]=fa[i];
while(top)Pushdown(stack[top--]);
int y,z;
for(y=fa[x],z=fa[y];y!=pos;z=fa[y=fa[x]]){
bool f1=(ch[y][1]==x),f2=(ch[z][1]==y);
if(z==pos)Rotate(x,f1);
else if(f1^f2)Rotate(x,f1),Rotate(x,f2);
else Rotate(y,f2),Rotate(x,f1);
}
Update(x);
if(pos==0)rt=x;
}
inline void Insert(int value){
if(++cnt != 1){
Splay(cnt-1,0);
fa[cnt]=rt;val[cnt]=value;ch[rt][1]=cnt;
size[cnt]=1;size[rt]++;
}
else rt=cnt,size[rt]=1,val[cnt]=value;
}
inline int Find(int x){
int pos=rt;
while(true){
Pushdown(pos);
if(x<=size[ch[pos][0]])pos=ch[pos][0];
else if(x==size[ch[pos][0]]+1)return pos;
else x-=size[ch[pos][0]]+1,pos=ch[pos][1];
}
}
inline void Reverse(int l,int r){
Splay(Find(l),0),Pushdown(rt);
Splay(Find(r+2),rt),Pushdown(ch[rt][1]);
int u=ch[ch[rt][1]][0];
Pushdown(u),Tag[u]^=1;
swap(ch[u][0],ch[u][1]);
}
inline void Output(int u){
Pushdown(u);
if(ch[u][0])Output(ch[u][0]);
if(val[u])printf("%d ",val[u]);
if(ch[u][1])Output(ch[u][1]);
}
}Tree;
int main(){
int i,k,n;
#ifndef ONLINE_JUDGE
freopen("BZOJ1503.in","r",stdin);
freopen("BZOJ1503.out","w",stdout);
#endif
n=read();k=read();
Tree.Insert(0);
for(i=1;i<=n;i++)Tree.Insert(i);
Tree.Insert(0);
for(i=1;i<=k;i++){
int l=read(),r=read();
Tree.Reverse(l,r);
}
Tree.Output(Tree.rt);
puts("");
return 0;
}

总结

在这里讲的Splay只能算是Splay的入门吧。都是一些非常基本的操作,然而自己写得并不熟……还要好好加油啊!