浅谈 Splay
什么是 Splay
（Splay Tree），也叫分裂树，是一种，它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特（Daniel Sleator） 和 罗伯特·恩卓·塔扬（Robert Endre Tarjan 又是他）在1985年发明的。
（From 百度百科）
因为 Splay 是一颗二叉排序树，所以它的每一个节点都应该满足如下性质：
- 若左子树不空，则左子树上所有结点的值均小于或等于这个结点的值；
- 若右子树不空，则右子树上所有结点的值均大于或等于这个结点的值；
我们知道，在对二叉树进行中序遍历时，会先遍历左子树，然后是自身，最后才是右子树。所以一颗二叉排序树的中序遍历是不严格单调递增的。我们在进行重构树时，也需要保证中序遍历不变。
Splay 可以做什么
- 维护一个区间（
废话）； - 支持区间翻转；
- 支持求一个结点的前驱和后继；
- 支持求一个结点的排名；
- 支持求第\(k\)大；
Splay 需要维护的内容
int val[N];//当前结点的值int cnt[N];//有多少个重复结点int pre[N];//当前结点的父结点int siz[N];//以当前结点为根的子树大小int son[N][2];//当前结点的子结点([0]为左儿子，[1]为右儿子)bool rev[N];//是否翻转
Splay 支持的操作
get_dir 操作
这个操作的目的是确定一个节点是父节点的左儿子还是右儿子，返回值为0或1.
代码实现如下：
inline int get_dir(int x){ return son[pre[x]][1]==x;} push_up 操作
这个操作的目的是更新子树大小。
代码实现如下：
inline void push_up(int x){ siz[x]=siz[son[x][0]]+siz[son[x][1]]+cnt[x]; return;} rotate 操作
核心操作。 Splay 通过旋转操作来保持平衡。
每次旋转有两种不同情况的旋转，分别是当前结点是父亲结点的左儿子和右儿子。如果当前结点是父亲的左儿子，如下图，我们要把红点向上一层旋转：
为了方便，我们不妨令这颗树的中序遍历为 \(1-2-3-4-5-6-7\) 。如下图，2号点就是我们要旋转的点：
我们可以清楚的看出 rotate 的变化规律：
son[4][0]=3;pre[3]=4;//目标结点父亲的左儿子->目标结点的右儿子son[6][0]=2;pre[2]=6;//目标结点爷爷的（左/右）儿子->目标结点son[2][1]=4;pre[4]=2;//目标结点的右儿子->目标结点的父亲
同理，我们可以看出当前结点是父亲的右儿子时的规律（图中6号结点是目标结点）：
son[4][1]=5;pre[5]=4;//目标结点父亲的右儿子->目标结点的左儿子son[2][1]=6;pre[6]=2;//目标结点爷爷的（左/右）儿子->目标结点son[6][0]=4;pre[4]=6;//目标结点的左儿子->目标结点的父亲
归纳一下，可以得出以下步骤：
- 求出目标结点位于父亲结点的方向，并作为基本方向；
- 目标结点父亲的同向儿子->目标结点的异向儿子；
- 目标结点爷爷的（左/右）儿子->目标结点；
- 目标结点的异向儿子->目标结点的父亲；
代码实现如下：
inline void rotate(int x){ int f=pre[x],g=pre[f],d=get_dir(x),s=son[x][d^1]; son[f][d]=s; pre[s]=f; son[g][get_dir(f)]=x; pre[x]=g; son[x][d^1]=f; pre[f]=x; push_up(f); push_up(x); return;} splay 操作
这个操作的目的是将一个结点一直旋转至目标结点的儿子，如果目标结点为0，则表示旋转至根节点。
其实只需要每次进行旋转后判断父亲是不是目标结点，如果爷爷，父亲与当前结点“三点一线”，我们就要先旋转父节点，再旋转当前结点，使这颗 Splay 更平衡（代码实现如下：
void splay(int x,int tar=0){ while(pre[x]!=tar) { int f=pre[x],g=pre[f]; if(g!=tar) { if(get_dir(x)==get_dir(f)) rotate(f); else rotate(x); } rotate(x); } if(!tar) root=x; return;} find 操作
这是一个辅助操作，目的是把最大的小于等于指定值的结点 splay 到根节点。
操作很简单，只需要在每个结点处判断当前结点值是否小于指定值，再决定向左或向右,最后把找到的值 spaly 上来。代码实现如下：
void find(int v){ int x=root; if(!x) return; while(son[x][v>val[x]]&&val[x]!=v) { x=son[x][v>val[x]]; } splay(x); return;} updating……