写在前面： 部分来自孙宝（@Steven24）的博客，表示感谢。
认识
什么是Splay
就是BST的一种，整体效率是很高的，均摊的次数是O(logn)级别的。
基本操作就是把节点旋转到BST的root，从而改善BST的平衡性，但是很多人会在旋转中转晕
建议找个动图看看，或是上B站找个几分钟的视频看看就理解了。
烧烤
如何可以把一个节点旋转到BST的root的地方，这是Splay的核心，为了完成这个操作，我们主要是需要分成两步：
1.每旋转一次，就使得我们的目标节点x的层次上升一层，最后到达root层
2.在旋转完后，BST的平衡性被破坏了，这是毋庸置疑的，所以我们需要进行一系列的调整，使这棵BST重新回到平衡状态
显然，如果只考虑1，那么使用Treap树的旋转法即可，每次x与x的父亲交换位置（x上升一层）。可Treap树的这种“单旋”并不能减少BST的层数。
所以我们就升级一下，再拉来一个更能打的，祖父节点，让这三代人一起转。
Splay旋转
#define left 0,right 1
这个就是LL,RR,LR,RL四个Splay的基本模型
网上有很多
自己看吧
我推荐这个，因为我就是看着他弄懂的基础知识
Splay四种模型
Splay操作
由于支持单点旋转改变平衡因子的特性Splay常用于处理区间分裂和合并问题。
例如：一个常见的区间操作，修改或查询区间[L,R]，用Splay树就很容易实现：先把L-1旋转到根，然后把节点R+1旋转到L-1的右子树上，此时，L+1的左子树就是区间[L,R]。
1.旋转：
rotate(x)对x点进行一次旋转，若x是一个右儿子，左旋，反之亦反之。
Splay Rotate
void rotate(int x)//单旋一次
{int f=t[x].fa;//f：父亲int g=t[f].fa;//g：祖父int son=get(x);if(son==1)//x是左儿子，右旋{t[f].rs=t[x].ls;if(t[f].rs){t[t[f].rs].fa=f;}}else//x是右儿子，左旋{t[f].ls=t[x].rs;if(t[f].ls){t[t[f].ls].fa=f;}}t[f].fa=x;//x旋为f的父节点if(son==1)//左旋，f变为x的左儿子{t[x].ls=f;}else//右旋，f变为x的右儿子{t[x].rs=f;}t[x].fa=g;//x现在是祖父的儿子if(g)//更新祖父的儿子{if(t[g].rs==f){t[g].rs=x;}else{t[g].ls=x;}}Update(f);Update(x);
}Splay(int x,int goal),把节点x旋转到goal位置。goal=0表示把x旋转到根，x是新的根。goal≠0表示把x旋转为goal的儿子。
Splay Rotate Destiny
void Splay(int x,int goal)
{if(goal==0){root=x;}while(1){int f=t[x].fa;//一次处理x,f,g三个节点int g=t[f].fa;if(f==goal){break;}if(g!=goal)//有祖父，分为一字旋和之字旋两种情况{if(get(x)==get(f))//一字旋，先旋转f,g{rotate(f);}else//之字旋，直接旋转x{rotate(x);}}rotate(x);}Update(x);
} 2.分裂和合并：
Insert()、Del()函数中包含了分裂与合并，详情见代码注释。利用Splay函数实现分裂与合并，编码很简单。
Splay Insert and Delete
void Insert(int L,int len)//插入一段区间
{int x=kth(root,L);//x为第L个数的位置，y为第L+1个数的位置int y=kth(root,L+1);Splay(x,0);//分裂Splay(y,x);//先把x旋转到根，然后把y旋转到x的儿子，且y的儿子为空t[y].ls=build(1,len,y);//合并：建一棵树，挂到y的左儿子上Update(y);Update(x);
}
void Del(int L,int R)//删除区间[L+1,R]
{int x=kth(root,L)；int y=kth(root,R+1);Splay(x,0);//y是x的右儿子，y的左儿子是待删除的区间Splay(y,x);t[y].ls=0;//剪短左子树，等于直接删除，这里为了简单，没有释放空间Update(y);Update(x);
}3.查询：
Splay Find
int kth(int x) { //查询排名为x的数 int now = root;while (1) {if (siz[son[now][0]] >= x) now = son[now][0]; //查过头了else if (siz[son[now][0]] + cnt[now] >= x) return val[now]; //正好查到else {x -= (siz[son[now][0]] + cnt[now]);now = son[now][1]; //没查够 } }
}Splay Rank
int rank(int x) { //查询x的排名 int now = root, ans = 0;while (1) {if (!now) return ans + 1; //树中不存在这个数 那就是目前查到比它小的数的数目+1if (val[now] > x) now = son[now][0]; //要查的数比now节点的数小 说明在左子树else if (val[now] == x) {ans += siz[son[now][0]]; //比它小的数的数目splay(now);return ans + 1; } else { //要查的数在左子树 ans += siz[son[now][0]] + cnt[now]; //此时当前节点和左子树所有数都比它小 now = son[now][1];}}
}Splay Find pre/nxt
int findpre() { //查询根节点的前驱对应的结点编号 int now = son[root][0]; //首先进入左子树 因为左子树的所有数都比它小 while (son[now][1]) now = son[now][1]; //然后一直往大的走 找最大的return now;
} int findnxt() { //跟上面同理 int now = son[root][1];while (son[now][0]) now = son[now][0];return now;
}···else if (opt == 5) {splay.insert(x); //把x先旋到根节点 而且一定要插入而不是直接旋 防止树上本来就没有xprintf("%d\n", splay.val[splay.findpre()]);splay.del(x); //用完删掉
} else {splay.insert(x); //同上 printf("%d\n", splay.val[splay.findnxt()]);splay.del(x);
}注意
（感谢孙宝）
所以 splay 容易写挂的原因找到了 要是哪个 splay 和 maintain 忘写了就寄了
那么怎么记住到底哪要写哪不用写呢
对于 maintain 很简单 改了啥就把它自己 maintain 一下 再把父亲（如果有）也 maintain 一下
对于 splay 实际上我们使用这个函数的同时如果要实现提根的功能 那就写
比如 insert 我们查询前驱后继需要使用它并且把插入的数旋到根 所以要写
比如 rank 我们就是要用它把权值为 x 的结点旋到根节点 所以要写
再比如 del 呃这个你肯定不能忘
如果还记不住怎么办呢
首先要明确 splay 是复杂度的保证 写少了复杂度就会假
但是写几个肯定是没事的
maintain 也是 如果该更新的没更新肯定就寄了
但是把没必要更新的也更新了问题就不大
所以实在不行这俩就是能写就写
当然这么干常数就又会变大 所以最好还是记一下上面那个
