之前学了fhq—Treap，一种靠分裂与合并维护平衡的一种树，期望复杂度是logn，常数也较大。Treap也有带旋转版本的，但是为了早日学会LCT还是先学Splay。也建议初学者先学不带旋转的平衡树，当然还有更简单的替罪羊树也可以先学。先借简单的来了解为什么要这样做。然后学更难的就跟好理解了。
BST（二叉搜索树）的缺点是容易被卡成链，所以我们想要通过某种方法来使它的树高不那么任意被卡。我理解的平衡树就是为了使BST保持平衡，即树的高度期望是logn，或者每种操作均摊logn。保证了复杂度的情况下，就可以把平衡树当作二叉搜索树来用拉。Treap借助的是Heap，使他的树高的期望是logn。而Splay利用的是旋转，让它的树形始终在变化（以万变应不变），使得每个操作均摊logn（证明是用了势能分析，很多博客都讲了证明方法，这里不说了。其实是不会 ）。只是自己的拙见，若有不对还望大佬指出。
我们把splay最基本的操作称为Zig（左旋）和Zag（右旋），每次旋转后保证它的中序遍历不变。（treap每次操作也是保证中序遍历不变）。对于BST来说有用的只有中序遍历，因为中序遍历可以得出有序的序列。所以我们也必须要保证中序遍历不变。理解左旋和右旋一定要从中序遍历不变的角度理解。
中序遍历是axbycz,经过转换后中序遍历不变。 可以把（a,x)，（b），（y，c）当成三个不同的部分，走完x之后下一个要走的是b，而(y,c)已经成为了右儿子，为了先去b，把b连到y的左儿子处。
左旋也是类似，这里就放个图不解释了。
Zig和Zag做的事情就是把当前的节点往上旋，把父节点变成你的子节点(认子做父？）。 我们先给出代码：
struct node { int ch[2], fa;// ch[0]为左儿子， ch[1]为右儿子，fa为父亲 }T[N]; void rotate(int x) { int y = T[x].fa; // 父亲节点 int z = T[y].fa; // 祖父节点 int k = T[x].ch[1] == x; //判断是左儿子还是右儿子 T[z].ch[T[z].ch[1]==y] = x; T[x].fa = z;// 认祖父当爹 T[y].ch[k] = T[x].ch[k^1]; T[T[x].ch[k^1]]=y; // 认孙子当儿子 T[x].ch[k^1] = y; T[y].fa = x; // 认子当爹 }建议大家理解了左旋右旋后自己独立写几遍。
splay操作才是Splay最核心的部分。我们观察上面的Zig和Zag，我们把x旋到根，如果我们只对x这个点执行两次Zig或者只执行两次Zag，你会发现它的最长链始终没有改变。这样的话Splay就容易被卡。所以一般都是分不同的情况选择旋转的点，例如第一个图，我们先旋转y，再旋转x。你会发现最长链没了（变成了另外一条，虽然长度看起来一样长）。
总的来说，总共就两种情况，一种是三个点都在同一侧。如下图 我们先旋转y，再旋转x。
另外一种就是不在同一侧。如下图 我们旋转两次x即可。还有一些情况是没有z节点的，我们直接旋转x就行。
然后我们发现无论怎么样都会执行一次旋转x，只需要判断是否需要先旋转y即可。 给出代码：
int root; // 全局根节点 void splay(int x, int rt) { // 把x旋转到rt的儿子，若rt为0则旋转到根 while(T[x].fa != rt) { // 若没有旋到rt的儿子 int y = T[x].fa, z = T[y].fa; // 找父节点和祖父节点 if(z != rt) (T[z].ch[0] == y) ^ (T[y].ch[0] == x) ? rotate(x), rotate(y); // 若有三个点则按照上面分析的旋转 rotate(x);// 无论怎么样都要旋转x } if(rt == 0) root = x; }然后剩下的就是一些Splay要注意的地方了。每次操作都执行splay函数，除非是用不上的，例如第k大查询。这样做是为了均摊复杂度。感性理解就是虽然某一刻可能变成了链，但是下一刻就改变了，除非写挂了，不然数据是卡不掉的。 我们就用P3369 【模板】普通平衡树 来讲一下各个操作的要点。
上传标记和下传标记和线段树的方法是一样的在变化的地方上传，被改过且要用的地方下传。这里不涉及下传，就不写了。
struct node { int ch[2], fa;// ch[0]为左儿子， ch[1]为右儿子，fa为父亲 int val, cnt, siz; // 该点的权值，该点重复的次数，它及它儿子的数的数量 }T[N]; int root, cnt; // 全局根节点 void up(int rt) { T[rt].siz = T[rt].cnt + T[T[rt].ch[0]].siz + T[T[rt].ch[1]].siz; } void rotate(int x) { int y = T[x].fa; // 父亲节点 int z = T[y].fa; // 祖父节点 int k = T[y].ch[1] == x; //判断是左儿子还是右儿子 T[z].ch[T[z].ch[1]==y] = x; T[x].fa = z;// 认祖父当爹 T[y].ch[k] = T[x].ch[k^1]; T[T[x].ch[k^1]].fa=y; // 认孙子当儿子 T[x].ch[k^1] = y; T[y].fa = x; // 认子当爹 up(y); up(x); //只有x和y需要更新 } void splay(int x, int rt) { // 把x旋转到rt的儿子，若rt为0则旋转到根 while(T[x].fa != rt) { // 若没有旋到rt的儿子 int y = T[x].fa, z = T[y].fa; // 找父节点和祖父节点 if(z != rt) (T[z].ch[0] == y) ^ (T[y].ch[0] == x) ? rotate(x): rotate(y); // 若有三个点则按照上面分析的旋转 rotate(x);// 无论怎么样都要旋转x } if(rt == 0) root = x; } int new_node(int x, int fa) { int rt = ++cnt; if(fa) T[fa].ch[x > T[fa].val] = rt; T[rt].ch[0] = T[rt].ch[1] = 0; T[rt].fa = fa; T[rt].siz = T[rt].cnt = 1; T[rt].val = x; return rt; }注意：为了方便起见，我们默认插入了一个负无穷和正无穷
我们先从简单的操作开始，首先是查找前驱和后继。 前驱和后继的方法差不多，由于可能没有前驱和后继，插入正负无穷就可以少判断很多情况。你会发现查找前驱和后继都记录了fa，这个变量在删除的时侯有用。最后记得splay
int pre(int x) { // 查找前驱 int fa, an; for(int rt(root); rt; ) { if(T[rt].val >= x) rt = T[rt].ch[0]; else an = T[fa = rt].val, rt = T[rt].ch[1]; } splay(fa, 0); return an; } int nxt(int x) { // 查找后继 int fa=root, an; for(int rt(root); rt; ) { if(T[rt].val <= x) rt = T[rt].ch[1]; else an = T[fa=rt].val, rt = T[rt].ch[0]; } splay(fa, 0); return an; }然后是查找排名和查找k小数。 查找x的排名的时侯，由于可能没有这个数，所以我用一个变量fa记录了它的父节点，这样最后就可以splay一下了。
int _rank(int x) { // 找到数x是第几小 int k(0), rt(root), fa = rt; while(rt) { fa = rt; if(T[rt].val == x) { splay(rt, 0); return T[T[rt].ch[0]].siz; } else if(T[rt].val < x) k += T[rt].cnt + T[T[rt].ch[0]].siz, rt = T[rt].ch[1]; else rt = T[rt].ch[0]; } if(!fa) splay(fa, 0);// 虽然一定找得到，但还是保险起见 return k; } int _kth(int x) { // 第x小的数是多少，这个要是超出了总数，直接return吧，不然就一定会splay if(x > T[root].siz) return INF; int k(1); for(int rt(root); rt;) { if(k + T[T[rt].ch[0]].siz <= x and x < k + T[rt].cnt + T[T[rt].ch[0]].siz) { splay(rt, 0); return T[rt].val; } else if(x < k + T[T[rt].ch[0]].siz) rt = T[rt].ch[0]; else k += T[T[rt].ch[0]].siz + T[rt].cnt, rt = T[rt].ch[1]; } }然后是插入和删除。splay最恶心的就是删除操作，要考虑很多情况，比如这个数不存在，如果不存在不是简简单单的return，你要判断它是否存在肯定要去遍历树，而遍历了树你就得splay一下，由于这个点不存在，所以你要记录它的父亲，想想就挺麻烦的。然后在网上找到了一个很精简的写法。找到前驱和后继，把后继splay到前驱的儿子处，然后你会发现该点一定在后继节点的左儿子，如果它存在的话。不存在就直接splay一下后继就行。存在的话看一下它是不是大于1个，若是则直接减一就行，否则删除这个节点。虽然复杂度高了点，但是好写多了。 这里也能看到先插入正负无穷的好处，就是前驱和后继一定存在。 比较简短的代码：
void insert(int x) { int rt = root, fa = 0; while(rt && T[rt].val != x) { fa = rt; rt = T[rt].ch[x > T[rt].val]; } if(rt) T[rt].cnt++; else rt = new_node(x, fa); splay(rt, 0); } void del(int x) { nxt(x); int ne = root; pre(x); int la = root; splay(ne, la); int del = T[ne].ch[0]; if(T[del].val != x) return ; if(T[del].cnt > 1) splay(del, 0), T[del].cnt--, T[del].siz--; else T[ne].ch[0] = 0, splay(ne, 0); }完整代码：
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const double Pi = acos(-1); namespace { template <typename T> inline void read(T &x) { x = 0; T f = 1;char s = getchar(); for(; !isdigit(s); s = getchar()) if(s == '-') f = -1; for(; isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48); x *= f; } } #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define _for(n,m,i) for (register int i = (n); i < (m); ++i) #define _rep(n,m,i) for (register int i = (n); i <= (m); ++i) #define _srep(n,m,i)for (register int i = (n); i >= (m); i--) #define _sfor(n,m,i)for (register int i = (n); i > (m); i--) #define lson rt << 1, l, mid #define rson rt << 1 | 1, mid + 1, r #define lowbit(x) x & (-x) #define pii pair<int,int> #define fi first #define se second const int N = 1e5+5; struct node { int ch[2], fa;// ch[0]为左儿子， ch[1]为右儿子，fa为父亲 int val, cnt, siz; // 该点的权值，该点重复的次数，它及它儿子的数的数量 }T[N]; int root, cnt; // 全局根节点 void up(int rt) { T[rt].siz = T[rt].cnt + T[T[rt].ch[0]].siz + T[T[rt].ch[1]].siz; } void rotate(int x) { int y = T[x].fa; // 父亲节点 int z = T[y].fa; // 祖父节点 int k = T[y].ch[1] == x; //判断是左儿子还是右儿子 T[z].ch[T[z].ch[1]==y] = x; T[x].fa = z;// 认祖父当爹 T[y].ch[k] = T[x].ch[k^1]; T[T[x].ch[k^1]].fa=y; // 认孙子当儿子 T[x].ch[k^1] = y; T[y].fa = x; // 认子当爹 up(y); up(x); //只有x和y需要更新 } void splay(int x, int rt) { // 把x旋转到rt的儿子，若rt为0则旋转到根 while(T[x].fa != rt) { // 若没有旋到rt的儿子 int y = T[x].fa, z = T[y].fa; // 找父节点和祖父节点 if(z != rt) (T[z].ch[0] == y) ^ (T[y].ch[0] == x) ? rotate(x): rotate(y); // 若有三个点则按照上面分析的旋转 rotate(x);// 无论怎么样都要旋转x } if(rt == 0) root = x; } int new_node(int x, int fa) { int rt = ++cnt; if(fa) T[fa].ch[x > T[fa].val] = rt; T[rt].ch[0] = T[rt].ch[1] = 0; T[rt].fa = fa; T[rt].siz = T[rt].cnt = 1; T[rt].val = x; return rt; } void insert(int x) { int rt = root, fa = 0; while(rt && T[rt].val != x) { fa = rt; rt = T[rt].ch[x > T[rt].val]; } if(rt) T[rt].cnt++; else rt = new_node(x, fa); splay(rt, 0); } int _rank(int x) { // 找到数x是第几小 int k(0), rt(root), fa = rt; while(rt) { fa = rt; if(T[rt].val == x) { splay(rt, 0); return T[T[rt].ch[0]].siz; } else if(T[rt].val < x) k += T[rt].cnt + T[T[rt].ch[0]].siz, rt = T[rt].ch[1]; else rt = T[rt].ch[0]; } if(!fa) splay(fa, 0); return k; } int _kth(int x) { // 第x小的数是多少 if(x > T[root].siz) return INF; int k(1); for(int rt(root); rt;) { if(k + T[T[rt].ch[0]].siz <= x and x < k + T[rt].cnt + T[T[rt].ch[0]].siz) { splay(rt, 0); return T[rt].val; } else if(x < k + T[T[rt].ch[0]].siz) rt = T[rt].ch[0]; else k += T[T[rt].ch[0]].siz + T[rt].cnt, rt = T[rt].ch[1]; } } int pre(int x) { // 查找前驱 int fa, an; for(int rt(root); rt; ) { if(T[rt].val >= x) rt = T[rt].ch[0]; else an = T[fa = rt].val, rt = T[rt].ch[1]; } splay(fa, 0); return an; } int nxt(int x) { // 查找后继 int fa=root, an; for(int rt(root); rt; ) { if(T[rt].val <= x) rt = T[rt].ch[1]; else an = T[fa=rt].val, rt = T[rt].ch[0]; } splay(fa, 0); return an; } void del(int x) { nxt(x); int ne = root; pre(x); int la = root; splay(ne, la); int del = T[ne].ch[0]; if(T[del].val != x) return ; if(T[del].cnt > 1) splay(del, 0), T[del].cnt--, T[del].siz--; else T[ne].ch[0] = 0, splay(ne, 0); } int main() { insert(-INF); insert(INF); int n, op, x; read(n); while(n--) { read(op); read(x); switch(op) { case 1: insert(x); break; case 2: del(x); break; case 3: printf("%d\n", _rank(x)); break; case 4: printf("%d\n", _kth(x+1)); break; case 5: printf("%d\n", pre(x)); break; case 6: printf("%d\n", nxt(x)); break; } } }感觉Splay比fhq-Treap难写多了，要注意的地方也很多。但是Splay很灵活，所以它被选为LCT的辅助树，学这个也是为了学LCT。马上滚去学LCT了
