文艺平衡树 Splay，也叫伸展树、分裂树，是一种二叉排序树，它能快速完成插入、查找和删除操作。它是由丹尼尔·斯立特 Daniel Sleator 和 罗伯特·恩卓·塔扬 Robert Endre Tarjan 在 1985 年发明的。

$\text{Splay}$ 是一种强大的数据结构。

简介

$\text{Splay}$ 的本质是一颗进化的二叉查找树。

但它与普通的二叉查找树相比，难度较大，所以常常有人说“去掉 S 我就会”（play），“去掉 p 我就会”（Slay，一款游戏）或者去掉 Sp 我就会（lay，指 躺着）。

下面介绍一下它的基本信息。

存储结构

用 root 表示整棵树的根节点编号。

编号为 $i$ 的节点存储：

• 父亲节点的编号，用 fa[i] 表示；
• 左右儿子节点的编号（没有一般设置成 $0$），用ch[i][0/1] 表示，ch[i][0] 表示左儿子，ch[i][1] 表示右儿子；
• 当前节点的键值，用 val[i] 表示；
• 以当前节点为根的子树大小，用 size[i] 表示；
• 以当前节点内包含的元素个数，用 cnt[i] 表示。

基本操作

为了更加方便的操作

1. $\operatorname{pushup}(x)$
   将编号为 $x$ 的节点的信息（主要指 size[x]）更新。

    

   inline void pushup(reg int x){
       size[x]=sizez[ch[x][0]]+sz[ch[x][1]]+cnt[x];
       return;
   }
   

2. $\operatorname{get}(x)$
   查询当前节点是该节点父亲节点的左儿子还是右儿子，左儿子返回 $0$（false），右儿子返回 $1$（true）。

    

   inline bool get(reg int x){
       return x==ch[fa[x]][1];
   }
   

3. $\operatorname{clear}(x)$
   清空编号为 $x$ 的节点上储存的信息。

    

   inline void clear(reg int x){
       fa[x]=ch[x][0]=ch[x][1]=0;
       val[x]=size[x]=cnt[x]=0;
       return;
   }
   

核心操作

1. $\operatorname{rotate}(x)$
   将 $x$ 旋转到原来父亲节点的位置上，同时不改变整棵树的中序遍历。
   下面我们考虑两种情况：
   $x$ 是父亲节点的左儿子。
   
   $x$ 是父亲节点的右儿子。
   
   于是可以写出代码。

    

   inline void rotate(reg int x){
       reg int f=fa[x],ff=fa[f];
       pushdown(x),pushdown(f); //这里的是魔改后的 Splay，所以与正常的有点不同
       bool w=get(x);
       ch[f][w]=ch[x][w^1];
       fa[ch[f][w]]=f;
       fa[f]=x;
       fa[x]=ff;
       ch[x][w^1]=f;
       if(ff)
           ch[ff][ch[ff][1]==f]=x;
       update(f); //这里的是魔改后的 Splay，所以与正常的有点不同
       return;
   }
   

2. $\operatorname{splay}(x,\text{goal})$
   将 $x$ 转动到 $\text{goal}$ 的儿子位置（$\text{goal}=0$ 表示把 $x$ 移到根节点的位置上）。

    

   inline void splay(reg int x,reg int goal){
       for(reg int qwq;(qwq=fa[x])!=goal;rotate(x))
           if(fa[qwq]!=goal)
               rotate(get(x)==get(qwq)?qwq:x);
       if(goal==0)
           root=x;
       return;
   }
   

3. $\operatorname{insert}(x)$
   插入键值为 $x$ 的节点。
   插入操作是一个比较复杂的过程，具体步骤如下：

    

   • 如果树空了则直接插入根并退出。
   • 如果当前节点的权值等于 $x$ 则增加当前节点的大小并更新节点和父亲的信息，将当前节点进行 $\operatorname{splay}$ 操作。
   • 否则按照二叉查找树的性质向下找，找到空节点就插入即可（当然别忘了 $\operatorname{splay}$ 操作哦）。

4. $\operatorname{find}(x)$
   查找键值为 $x$ 的节点的编号。
   二分查找。

5. $\operatorname{kth}(x)$
   求排名为 $x$ 的节点的权值。
   查找过程有点像权值线段树。

6. $\operatorname{pre}(x)$
   查询 $x$ 的前驱。
   前驱定义为小于 $x$ 的最大的数，那么查询前驱可以转化为：将 $x$ 插入（此时 $x$ 已经在根的位置了），前驱即为 $x$ 的左子树中最右边的节点，最后将 $x$ 删除即可。

7. $\operatorname{nxt}(x)$
   查询 $x$ 的后继。
   后继定义为大于 $x$ 的最小的数，那么查询后继可以转化为：将 $x$ 插入（此时 $x$ 已经在根的位置了），后继即为 $x$ 的右子树中最左边的节点，最后将 $x$ 删除即可。

8. $\operatorname{del}(x)$
   删除 $x$。
   把 $x$ 转到根然后像二叉查找树一样删除。

注意事项

1. 查询前驱或后继时左右子树必须存在，不然有的写法容易死循环，所以推荐先插入正负无穷作为哨兵节点防止出错。
2. 不要随意地魔改 $\text{Splay}$，它太神奇了，改之前记得画画图。