编者注：（为了更好的理解Splay，需要读者对Treap有一定的了解）
那么话不多说，我们直接进入正题吧：
什么是Splay
伸展树（Splay Tree），也叫分裂树，是一种二叉排序树，它能在O(log n)内完成插入、查找和删除操作。
学过Treap的人或许会问那么Treap和Splay到底有什么区别呢？
其实很简单，相比于Treap，Splay能够更好的处理区间的问题，虽然Treap好像也可以进行区间操作，但是现在基本没人用了。但值得注意的是Treap的常数很小而Splay常数较大.
Splay能干什么？？
- 伸展操作 ： 在保持伸展树有序性的前提下，通过一系列旋转将伸展树S中的元素x调整至树的根部。
- 查找操作 ： Find(x,S)：判断元素x是否在伸展树S表示的有序集中。
- 加入操作 ： Insert(x,S)：将元素x插入伸展树S表示的有序集中。
- 删除操作 ： Delete(x,S)：将元素x从伸展树S所表示的有序集中删除。
- 合并操作 ： join(S1,S2)：将两个伸展树S1与S2合并成为一个伸展树。其中S1的所有元素都小于S2的所有元素
- 启发式合并 ： 当S1和S2元素大小任意时，将规模小的伸展树上的节点一一插入规模大的伸展树，总时间复杂度O(Nlg^2N)。
- 划分操作 ： Split(x,S)：以x为界，将伸展树S分离为两棵伸展树S1和S2，其中S1中所有元素都小于x，S2中的所有元素都大于x。
- 其他操作 ： 除了上面介绍的五种基本操作，伸展树还支持求最大值、求最小值、求前趋、求后继等多种操作，这些基本操作也都是建立在伸展操作的基础上的。
复杂度的保证
经证明，splay的复杂度是均摊logn的，由于splay没有像其他平衡树的旋转所以要用双旋来保证其不会退化成一条链，即将splay的深度保持在logn左右。
本文变量名解释：
- son[x][0/1]表示x的左右儿子
- fa[x]表示x的父亲节点
- cnt[x]这个节点的个数
- size[x]表示子树x的大小
- root表示根节点
- val[x]表示节点x的权值
基本操作
-
插入（inset）
从根节点开始搜索val，如果已经存在，直接将cnt++，否则新开一个点连到它的父亲上。双旋保证复杂度。
inline void insert(int x)
{
int cur=root,p=0;
while(cur&&val[cur]!=x)//搜到x；
{
p=cur;
cur=son[cur][x>val[cur]];
}
if(cur) cnt[cur]++;
else
{
cur=++ndnum;
if(p) son[p][x>val[p]]=cur;
son[cur][0]=son[cur][1]=0;val[cur]=x;fa[cur]=p;
cnt[cur]=size[cur]=1;
}
splay(cur);
}
-
旋转
其实旋转和Treap的一样，就直接看代码吧
inline void rotate(int x)
{
int y=fa[x],z=fa[y],kind=chk(x),w=son[x][kind^1];
son[y][kind]=w;fa[w]=y;
son[z][chk(y)]=x;fa[x]=z;
son[x][kind^1]=y;fa[y]=x;
update(y),update(x);
}
-
伸展（splay）
将一个节点一路rotate到指定节点的儿子。
注意，如果该节点、该父节点和该爷爷节点「三点一线」，那么应该先旋转父节点。此处进行的操作是将3 splay到根节点。
并且注意处理爷爷节点已经是目标的情况
代码如下：
inline void splay(int x,int goal=0)
{
while(fa[x]!=goal)
{
int y=fa[x],z=fa[y];
if(z!=goal)
{
if(chk(x)==chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if(!goal) root=x;
}
-
k大（kth）
从根节点开始，一路搜索下去。每次判断要走向哪个子树。注意考虑重复权值。
代码如下：
int kth(int x)
{
int cur=root;
while(1)
{
pushdown(cur);
if(son[cur][0]&&x<=size[son[cur][0]])
cur=son[cur][0];
else if(x>size[son[cur][0]]+cnt[cur])
{
x-=size[son[cur][0]]+cnt[cur];
cur=son[cur][1];
}
else
return cur;
}
}
- 向上统计（update）
- 代码如下：
inline void update(int rt)
{
size[rt]=size[son[rt][0]]+size[son[rt][1]]+cnt[rt];
return;
}
-
判断左右子树（chk）
代码如下：
inline int chk(int x)
{
return son[fa[x]][1]==x;
}
-
删除（remove）
求出该点的的前驱，后为。
那么可以考虑把前驱splay到根，后继splay到前驱的右儿子，那么后继的左儿子就是要删除的点。
代码如下:
inline void remove(int x)
{
int last=pre(x),next=back(x);
splay(last);splay(next,last);
int del=son[next][0];
if(cnt[del]>1)
{
cnt[del]--;
splay(del);
}
else son[next][0]=0;
}
-
查找（find）
将最大的小于等于x的数所在的节点splay到根。
代码如下：
inline void find(int x)
{
if(!root) return;
int cur=root;
while(son[cur][x>val[cur]]&&x!=val[cur])
{
cur=son[cur][x>val[cur]];
}
splay(cur);
}
-
查询x的排名
并不需要专门写操作。将该节点find到根后返回左子树的权值数即可。
find(x);
printf("%d\n",size[son[root][0]]);
- 前驱与后继（pre/back）
-
前驱：
将该节点find到根后返回左子树最右边的节点即可。
inline int pre(int x)
{
find(x);
if(val[root]<x) return root;
int cur=son[root][0];
while(son[cur][1])
{
sur=son[cur][1];
}
return cur;
}
- 后继同理（略）
好了让我们看一看例题吧：
题目背景
这是一道经典的Splay模板题——文艺平衡树。
题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
输入输出格式
输入格式：
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2,⋯n−1,n) (1,2, \cdots n-1,n)(1,2,⋯n−1,n) m表示翻转操作次
接下来m行每行两个数 [l,r][l,r][l,r] 数据保证 1≤l≤r≤n 1 \leq l \leq r \leq n 1≤l≤r≤n
输出格式：
输出一行n个数字，表示原始序列经过m次变换后的结果
这里就要用到splay区间处理的功能了，
对于区间【l，r】，我们把l-1旋转到根节点，将r+1旋转到根的右儿子，那么这个右儿子的左子树的中序遍历就是区间【l，r】。
这就是splay处理区间的根本原理。！！！很重要。
其实这道题一个节点的左右儿子交换后的中序遍历就是反转后的区间，那么要如何维护这个区间呢？？？
从线段树的启发中，我们能够想到用标记的方法来标记下传。这样就完美的解决了问题。
- 翻转（reverse）
inline void pushdown(int rt)
{
if(rev[rt])
{
swap(son[rt][0],son[rt][1]);
rev[son[rt][0]]^=1,rev[son[rt][1]]^=1;
rev[rt]=0;
}
}
inline void reverse(int l,int r)
{
int x=kth(l),y=kth(r+2);
splay(x),splay(y,x);
rev[son[y][0]]^=1;
}
最终代码：
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int fa[maxn],son[maxn][2],size[maxn],rev[maxn],root,cnt[maxn],ndnum=0,val[maxn];
int n,m;
inline int chk(int x)
{
return son[fa[x]][1]==x;
}
inline void update(int rt)
{
size[rt]=size[son[rt][0]]+size[son[rt][1]]+cnt[rt];
return;
}
inline void pushdown(int rt)
{
if(rev[rt])
{
swap(son[rt][0],son[rt][1]);
rev[son[rt][0]]^=1,rev[son[rt][1]]^=1;
rev[rt]=0;
}
}
inline void rotate(int x)
{
int y=fa[x],z=fa[y],kind=chk(x),w=son[x][kind^1];
son[y][kind]=w;fa[w]=y;
son[z][chk(y)]=x;fa[x]=z;
son[x][kind^1]=y;fa[y]=x;
update(y),update(x);
}
inline void splay(int x,int goal=0)
{
while(fa[x]!=goal)
{
int y=fa[x],z=fa[y];
if(z!=goal)
{
if(chk(x)==chk(y)) rotate(y);
else rotate(x);
}
rotate(x);
}
if(!goal) root=x;
}
inline void insert(int x)
{
int cur=root,p=0;
while(cur&&val[cur]!=x)//搜到x；
{
p=cur;
cur=son[cur][x>val[cur]];
}
if(cur) cnt[cur]++;
else
{
cur=++ndnum;
if(p) son[p][x>val[p]]=cur;
son[cur][0]=son[cur][1]=0;val[cur]=x;fa[cur]=p;
cnt[cur]=size[cur]=1;
}
splay(cur);
}
inline void find(int x)
{
if(!root) return;
int cur=root;
while(son[cur][x>val[cur]]&&x!=val[cur])
{
cur=son[cur][x>val[cur]];
}
splay(cur);
}
inline int pre(int x)
{
find(x);
if(val[root]<x) return root;
int cur=son[root][0];
while(son[cur][1])
{
sur=son[cur][1];
}
return cur;
}
int kth(int x)
{
int cur=root;
while(1)
{
pushdown(cur);
if(son[cur][0]&&x<=size[son[cur][0]])
cur=son[cur][0];
else if(x>size[son[cur][0]]+cnt[cur])
{
x-=size[son[cur][0]]+cnt[cur];
cur=son[cur][1];
}
else
return cur;
}
}
inline void reverse(int l,int r)
{
int x=kth(l),y=kth(r+2);
splay(x),splay(y,x);
rev[son[y][0]]^=1;
}
void print(int x)
{
pushdown(x);
if(son[x][0]) print(son[x][0]);
if(val[x]&&val[x]<=n) printf("%d ",val[x]);
if(son[x][1]) print(son[x][1]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n+1;++i) insert(i);
for(int i=1;i<=m;++i)
{
int l,r;
scanf("%d%d",&l,&r);
reverse(l,r);
}
print(root);
return 0;
}
完