Splay(伸展树)
0. 准备工作
在试图学习 Splay 之前，我们需要对一下内容加以理解：
1. 神码是 Dfs 序
2. 神码是二叉树的旋转
3. 二叉树旋转之后为什么中序遍历不变 (极其重要)
4. 线段树区间操作是是什么原理
1.Splay 是神码
Splay 是一种最优秀比较优秀的数据结构，它支持很多操作 (几乎你想得到它就做得到)，但是缺点就是常数较大。
Splay 满足二叉搜索树的很多性质：
1. 有序性：伸展树中的每一个节点的值都大于左儿子，小于右儿子
2. 中序遍历不变性：伸展树无论经过怎样的旋转，中序遍历总是不变的，而且中序遍历肯定是升序遍历 (或者你也可以让他降序)
3. 自我调整性：简单说就是旋旋更健康：操作之后 Splay() 一下就可以维护树的健康度在 logn 左右 (每次操作的复杂度)，至于 Splay 是什么操作，待会会讲
2. 如何实现一棵简单的 Splay
首先，我们需要明确几个操作，以及它们的作用 。
请自行脑补这两个操作是如何进行的，然后我们再继续。
现在，我们需要将 x 节点向上转移，我们可以利用 zig 和 zag 操作。但是这也分多种情况。
所以以下就是将 x 节点旋转到根节点的操作
/*
wson 为判断自己是父亲的哪个儿子的函数,，0 左 1 右
*/
inline bool wson(int node){return tree[tree[node].fa].s[1]==node;}
inline void rot(int a)//有取反操作，可以很方便地执行 zig 或 zag 操作而不加判断
{
int f=tree[a].fa,g=tree[f].fa,p=wson(a),q=wson(f);
tree[f].s[p]=tree[a].s[!p], tree[a].s[!p]=f, tree[f].fa=a;//顺序很重要
if(tree[f].s[p])tree[tree[f].s[p]].fa=f;
if(tree[a].fa=g)tree[g].s[q]=a;
}
inline void splay(int node)
{
while(tree[node].fa)
if(!tree[tree[node].fa].fa)rot(node);//node 是根节点的子节点
else if(wson(node)!=wson(tree[node].fa))rot(node),rot(node);//链是弯的
else rot(tree[node].fa),rot(node);//链是直的
root=node;
}
好的，以上就是 Splay 最基本的操作之一，至于为什么要有这么多旋转法则，说白了就是为了让 Splay 树变健康。
3.Splay 的插入操作
简单的想，我们需要找到一个节点，新建它的左儿子或者右儿子。至于如何找到那个节点，我们就要用到 Splay 的有序性。根节点一定比左儿子大，右儿子小。
/*
当前的节点是 node, 他的爸爸是 fa. 如果 node==0, 说明这个节点就是我们要找的节点，
我们就给 fa 新建一个子节点。
*/
//为了在新建节点的同时它父节点的儿子可以被更新，我们传入的是&node
void insrt(int x,int fa,int &node)
{
if(!node){node=++cnt,tree[node].x=x,tree[node].fa=fa,splay(node);return;}
if(x<tree[node].x)insrt(x,node,tree[node].s[0]);
else if(x>tree[node].x)insrt(x,node,tree[node].s[1]);
}
4.Splay 的前驱后继
过程类似插入操作，请自行脑补
/*
同样，x 是寻找前驱后继的值，node 为节点
*/
int nxt(int x,int node)
{
if(!node)return +1e8;
if(tree[node].x==x){splay(node);return x;}
if(tree[node].x>x)return min(nxt(x,tree[node].s[0]),tree[node].x);
else return nxt(x,tree[node].s[1]);
}
int pre(int x,int node)
{
if(!node)return -1e8;
if(tree[node].x==x){splay(node);return x;}
if(tree[node].x<x)return max(pre(x,tree[node].s[1]),tree[node].x);
else return pre(x,tree[node].s[0]);
}
5.Splay 节点的删除
我们需要将要删除的点 Splay 到根节点，然后删掉它。这时候会留下两颗孤独的子树，不过没关系，我们可以合并这两棵树。
/*
传入要删除的数 (而不是节点编号)，将该数删除
*/
void smax()
{
int a=root;
while(t[a].s[1])a=t[a].s[1];
splay(a);
}
int find(int x,int a)
{
while(a)
{
if(t[a].x==x)return a;
else if(t[a].x<x)a=t[a].s[1];
else a=t[a].s[0];
}
return a;
}
void del(int a)
{
splay(find(a,root));
int rs=t[root].s[1],ls=t[root].s[0];
if(rs==0){t[root].s[0]=t[root].s[1]=t[root].f=0,root=ls,t[root].f=0;return;}
if(ls==0){t[root].s[0]=t[root].s[1]=t[root].f=0,root=rs,t[root].f=0;return;}
t[root].s[0]=t[root].s[1]=0;//先将根和子节点的联系断开
t[rs].f=t[ls].f=0;
root=ls;
smax();//将左子树的最大值转到根
t[root].s[1]=rs;//合并左右子树称为新的树
t[rs].f=root;
}
综上所述，刚才的 Splay 可以完成插入、删除、修改、前驱、后继等操作。但是可以更多吗？
进阶 Splay 操作
真不清楚为什么，网上关于这类知识的介绍少之又少。我们能做的只是看着大神们的题解，一脸懵逼。出于各种考虑（其实就是因为我不会），这里就只放思路，不提供代码了。
1.Splay 全局第 k 大
在刚才那棵简单 Splay 的节点中多保存一个值：子树大小。这样就可以根据子树大小来选择要查找的值在左子树还是右子树。如此方便。
2. 序列在 Splay 中的保存
由于 Splay 需要满足有序性，所以我们可以很好的用它来储存一个序列。一个一维的序列经过 Splay 的保存，变身成为了拓扑性质完全不同的一棵树。但是这棵树又可以完美的还原原序列，并且可以更快速的完成对原序列的操作。这就是 Splay 称为序列之王的原因吧。
我们对 Splay 单调性的要求只要改为：x 节点在原序列中的位置小于右儿子的位置大于左儿子的位置。我们就可以得到一棵 beautiful 的 Splay。
3.Splay 中子序列的提取
如果我们现在需要提取原序列 [l,r] 的区间，怎么做呢？
由于刚才我们讨论的 Splay 具有各种优良的性质，所以如果我们寻找区间 [l,r]，我们当然希望他们在一棵子树上。由于 Splay 的中序不变性，只要对它进行中序遍历就可以得到原序列。那么怎么做呢？
其实只需要把原序列第 (l-1) 位对应的节点 Splay 到根节点，再把节点 (r+1)Splay 到根节点的右儿子，那么节点 (r+1) 的左子树一定就是序列 [l,r]。是不是很神奇又很自然。
4.Splay 中序列的反转
这里就要用到线段树中常用的一中策略：懒惰标记。
如果我们要反转序列 [l,r]，我们就像 3.Splay 的序列提取 里一样，将 [l,r] 变成一个子树，然后给子树的根节点打上懒惰标记，告诉它这棵树已经被反转了
然后就是标记下传，代码大概是这样的
/*
下传 node 的反转标记
*/
void pushdown(int node)
{
if(tree[node].lazy)
{
swap(tree[node].son[0],tree[node].son[1]);
if(tree[node].son[0])tree[tree[node].son[0]].lazy^=1;
if(tree[node].son[1])tree[tree[node].son[1]].lazy^=1;
tree[node].lazy=0;
}
}