前言：
$\quad\quad$ 最近准备省选，把以前的笔记抽出来翻了翻，找到了不少 BUG…于是更新了一下。
$\quad\quad$ $\LaTeX$ 日常炸，建议 Goto 原网址 https://xjx885.coding-pages.com/post/splay-xue-xi-bi-ji/
$\quad\quad$ Update（20/06/15）：修复了细节问题（包括但不限于 $\LaTeX$ 和图片和大部分表达）。
$~\\$
正文：
$\quad\quad$ 二叉查找树（BST）： 一种二叉的，用于查找信息的，树形数据结构。
$\quad\quad$ 具体而言：BST 是一种二叉树，设其上某一节点的值为 $x$，则该节点左子树中的所有点权值都小于 $x$，右子树中所有节点都大于 $x$ （递归定义）。
$\quad\quad$ 为什么叫它查找树呢？因为 BST 支持对树中的 $\operatorname{Kth}$（第 K 大的数是多少） 和某一个值在树中的 $\operatorname{Rank}$（某个数是第几大） 的查询（我一直都不太很分得清 $\operatorname{Kth}$ 和 $\operatorname{Rank}$ ，下面可能会有地方把它们弄混）。
$\quad\quad$ 实现方式是：维护一个 $size$ 数组，记录每个节点的子树大小，查询时，从根节点开始，比较当前 $size$ 与给出信息的大小，然后逐层递归。
$\quad\quad$ 举个例子：当我们查询 $x$ 在 BST 中的排名时，我们先比较它与根节点 $y$ 的大小，如果 $x<y$，那么 $x$ 在 $y$ 左儿子对应子树中，如果 $x=y$ 那么 $x$ 就在根节点上，它的排名可以用 $size(lson(y))+1$ 表示，如果 $x>y$ 那么 $x$ 在 $y$ 右儿子对应子树中，此时左儿子对应子树中的节点和根节点一定小于 $x$，我们可以把答案加上 $size(lson(y))+1$。这层处理完后，递归进下一层即可。
$\quad\quad$ 代码这里就不放了，后面和 $Splay$ 的其它函数一起放。
$\quad\quad$ BST 复杂度看起来很优，是 $O(logn)$ 的，但实际效果不好，理由很简单：同一棵二叉查找树有很多不同的形态。
$\quad\quad$ 比如说由1 2 3 4 5构成的二叉查找树…可以是这样的：
$\quad\quad$ 也可以是这样的：
$\quad\quad$ 为什么多形态效果不好呢？因为这意味着出题人可以简单地构造一条链把你卡到 $O(n)$。
$\quad\quad$ 你可能会说： Q：哎呀，那不简单，我们随机打乱一下不就好了吗？
$\quad\quad$ A：那要是出题人要你支持插入操作，插着插着就成链了呢？
$\quad\quad$ Q：Emm…那我们每次操作的时候都打乱一下？
$\quad\quad$ A：每次操作都打乱整棵树，那复杂度得多大啊？
$\quad\quad$ Q：那我们能不能在每次操作时，进行尽量少的打乱操作，却使得整棵树保持 “平衡” 呢？
$\quad\quad$ 这篇文章的主角，就是这样一种特殊的，不断打乱的，二叉查找树。
$~\\$
$\quad\quad$ $Splay$，也叫伸展树，本质上类似二叉查找树，是一种平衡树…
$\quad\quad$ 什么叫平衡树？我们上面其实已经提到了，平衡树就是一类用各种方法使出题人没办法把我们卡成 $O(n)$ 的 BST。
$\quad\quad$ 我们上面还提到了一种 “平衡” 的方式：在每次操作时进行打乱。这是一个朴素但有效的想法（其实还有更朴素的，那就是替罪羊树的直接重构）。
$\quad\quad$ 这所谓的 打乱 操作，正对应着 $Splay$ 的伸展（$Splay$）。（严格来讲，这不能叫打乱，要叫平衡）
$\quad\quad$ $Splay$ 主要分为两种，一种是维护权值的 $Splay$，一种是直接维护序列的 $Splay$，后者与一般 BST 有一定差异。
$\quad\quad$ 先介绍前者，维护权值的 $Splay$ 。它其实就是一棵可以自我平衡的 BST，BST 能处理的它能处理，BST 不能处理的它有可能也能处理，下面简单介绍它都能处理什么问题。
$~\\$
$\quad\quad$ 先给出变量列表，从这里面就可以看出很多东西了：
const int N=100010;
int num[N];//编号为i的点，代表的数值是多少...
int cnt[N];//编号为i的点，代表的数值出现了多少次...
int fa[N],son[N][2];//编号为i的点，父亲与左右儿子编号各是多少...
int size[N];//以编号为i的点为根的子树的节点的cnt的和是多少...
int tot;//计数工具：最后一个新建的点的编号是多少
int root;//Splay的根的编号是多少
$\quad\quad$ 我们一个一个看：
$\quad\quad$ $num$ 和 $cnt$ 好理解，我们一般的 BST 相同的元素是分成不同的点的，这里只不过把它们压缩成了一个点而已。
$\quad\quad$ $fa,son$ 也好理解，二叉树嘛，总要构建出树的结构的。
$\quad\quad$ $size$ 上面讲过了，用来处理操作的，也不难理解。
$\quad\quad$ 是不是突然发现 $Splay$ 的变量都挺好理解的？
$\quad\quad$ 下面看看 $Splay$ 的几大核心操作。
$~\\$
$rotate$（旋转）:
$\quad\quad$ 旋转，是我们的打乱操作的基础，也就是我们 $Splay$ 的核心： $Splay$ 操作的基础。
$\quad\quad$ 它的作用是：在不改变树的本质的前提下，调整几个节点之间的位置关系。
$\quad\quad$ 就像我们玩俄罗斯方块一样，先把方块转几圈，再放下去才能得高分。
$\quad\quad$ 上图：（以下所有点上的数字，仅代表该节点的编号，不代表该节点的数值）
$\quad\quad$ 这是一棵很 长 的树。看起来不是很平衡的样子......
$\quad\quad$ 我们让 $4$ 号节点上旋…得到：
$\quad\quad$ 是不是平衡多了？嗯？你说啥？你问这是咋操作的？
$\quad\quad$ 让我们来给这些节点染点颜色。
$\quad\quad$ 旋转前：
$\quad\quad$ 旋转后：
$\quad\quad$ 是不是稍微有点明白 “旋转” 啥意思了？
$\quad\quad$ 下面是详细的旋转步骤：
1：设旋转的节点为x点，其父节点为y点，祖父节点为z点...
2：设x是y的m儿子（m为0/1，代表左/右儿子，下同），y是z的n儿子...
3：把x的m^1儿子变为y的m儿子
4：把y变为x的m^1儿子
5：把x变为z的n儿子
6：更新操作后x,y的size值（为什么其他点不用更新？因为它们的儿子都没变的来着）
$\quad\quad$ 上面的 ^ 代表的是 $\oplus$，即异或。
$\quad\quad$ 虽然过程看起来很复杂，但其实只有 $3,4,5$ 三步比较关键，需要记忆。
$\quad\quad$ 下面是代码描述，从上到下分别于上面的步骤相对应：
void rotate(int x)
{
int y = fa[x], z = fa[y];
int m = find(x) , n = find(f);
connect(son[x][m ^ 1], y, m);
connect(y, x, m ^ 1);
connect(x, z, n);
push_up(y), push_up(x);
}
$\quad\quad$ 注意了：三个 $connect$ 和两个 $push_up$ 的顺序一定不能反。
$\quad\quad$ 对了，$find(),connect(),push_up()$是三个辅助函数，作用分别为：得到某个节点是它父亲的什么儿子；连接某两个点；更新某个点的$size$值…其代码如下：
int find(int x)
{
return son[fa[x]][1] == x ? 1 : 0;
}
void connect(int x, int y, int w_son)
{
if(y) son[y][w_son] = x;
if(x) fa[x] = y;
}
void push_up(int x)
{
size[x] = size[son[x][0]] + size[son[x][1]] + cnt[x];
}
$\quad\quad$ 注意了：$connect$函数一定不能把0点与其他点连起来，要么你在 $connect$ 里面判一下，要么你在以后调用 $connect$ 之前判一下。（这都是血的教训啊）
$~\\$
$Splay$（伸展）:
$\quad\quad$ 理解了 $rotate$ 之后， $Splay$ 就好理解了…如果说 $rotate$ 是旋转俄罗斯方块，那么 $Splay$ 就要通过一次次的旋转把俄罗斯方块消掉了。
$\quad\quad$ $Splay$ 本质是：把一个节点不断网上旋，直到到根（或者某指定节点）。
$\quad\quad$ 你可能很疑惑，为什么这样就可以把整棵树给平衡了…关于 $Splay$ 的均摊时间复杂度分析有很多论文，感兴趣可以搜一搜，这里就不详细讲了。
$\quad\quad$ $Splay$ 操作起来就很简单了，一直旋到根而已，代码如下。（下面代码压了行，所以可能有些难以理解，展开之后就好理解多了）
void Splay(int x)
{
for(int f; (f = fa[x]) != 0; rotate(x))
if(fa[f]) rotate(find(f) == find(x) ? f : x);
root = x;
}
$\quad\quad$ 不过，可以看出，旋转过程中有一个特殊情况：当旋转节点，旋转节点父节点，旋转节点祖父节点“三点一线”（旋转节点是父节点的m儿子，父节点也是祖父节点的m儿子）时，要先转一下父节点，再转一下当前节点…为什么？移步 $Splay$ 复杂度分析论文，请。
$\quad\quad$ 注意了：最后不要忘了把根赋给旋上来的节点（如果它是一直旋到根的话）。
$\quad\quad$ $Splay$ 这个平衡操作咋用呢？很简单，每次操作后给被操作节点一个 $Splay$ 就好。
$~\\$
$\quad\quad$ 接下来就直接上代码了…都是些常用的函数…
$~\\$
$Find$（得到某个点的排名）:
int Find(int x)
{
int now = root, ans = 0;
while(true)
{
if(x < num[now])
{
now = son[now][0];
continue;
}
ans += size[son[now][0]];
if(num[now] == x)
{
Splay(now);
return ans + 1;
}
ans += cnt[now];
now = son[now][1];
}
}
$~\\$
$Kth$（得到排行为x的节点的值）:
int Kth(int rank)
{
int now = root;
while(1)
{
if(rank <= size[son[now][0]])
{
now = son[now][0];
continue;
}
rank -= size[son[now][0]];
if(rank <= cnt[now])
{
Splay(now);
return num[now];
}
rank -= cnt[now];
now = son[now][1];
}
}
$~\\$
$Insert$（插入）:
$\quad\quad$ 这个函数要注意一下，好理解但操作比较多，不要掉了哪一个。
void Insert(int x)
{
if(root == 0)
root = ++tot, size[tot] = cnt[tot] = 1, num[tot] = x;
else
{
int now = root, f = 0;
while(true)
{
if(num[now] == x)
{
cnt[now]++;
push_up(now), push_up(f);
Splay(now);
return ;
}
f = now, now = son[now][x > num[now]];
if(!now)
{
num[++tot] = x, size[tot] = cnt[tot] = 1;
fa[tot] = f, son[f][x > num[f]] = tot;
push_up(f), Splay(tot);
return ;
}
}
}
}
$~\\$
$Delete$（删除）:
$\quad\quad$ 与一般 BST 的删除不同，因为我们有 $Splay$ 操作，所以我们可以通过 $Find$ 操作把要删的点直接转到根上来，然后分情况讨论处理就好，注意：要在操作前把原本的根记录下来，后面的 $Splay$ 操作会改变根（记录用的变量名不要和 $root$ 太像…我用 $rt$ 时弄混好多次了）。
$\quad\quad$ 这里的 $clear$ 操作就是一个简单的把某个点的各个数据全部清零的操作。
void Delete(int x)
{
Find(x);
int now = root;
if(cnt[now] > 1) cnt[now]--, size[now]--;
else if(!son[now][0] && !son[now][1])
root = 0, clear(now);
else if(!son[now][0] && son[now][1])
fa[root = son[now][1]] = 0, clear(now);
else if(son[now][0] && !son[now][1])
fa[root = son[now][0]] = 0, clear(now);
else
{
int pre = Pre(), rt = root, rson = son[root][1];
Splay(pre), connect(rson, pre, 1);
clear(rt), push_up(root);
}
}
$~\\$
$Pre$（得到根的前驱的编号）:
int Pre()
{
int now = son[root][0];
while(son[now][1])
now = son[now][1];
return now;
}
$~\\$
$Suc$（得到根的后继的编号）:
int Suc()
{
int now = son[root][1];
while(son[now][0])
now = son[now][0];
return now;
}
$\quad\quad$ 以上是$Splay$的基本操作。
- 代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int fa[N], son[N][2], cnt[N], num[N] , size[N];
int n, tot, root;
void clear(int x)
{
fa[x] = son[x][0] = son[x][1] = cnt[x] = num[x] = size[x] = 0;
}
int find(int x)
{
return son[fa[x]][1] == x ? 1 : 0;
}
void connect(int x, int y, int w_son)
{
if(y) son[y][w_son] = x;
if(x) fa[x] = y;
}
void push_up(int x)
{
size[x] = size[son[x][0]] + size[son[x][1]] + cnt[x];
}
void rotate(int x)
{
int f = fa[x], ff = fa[f] , k = find(x) , i = find(f);
connect(son[x][k ^ 1], f, k);
connect(f, x, k ^ 1);
connect(x, ff, i);
push_up(f), push_up(x);
}
void Splay(int x)
{
for(int f; (f = fa[x]) != 0; rotate(x))
if(fa[f]) rotate(find(f) == find(x) ? f : x);
root = x;
}
void Insert(int x)
{
if(root == 0)
root = ++tot, size[tot] = cnt[tot] = 1, num[tot] = x;
else
{
int now = root, f = 0;
while(true)
{
if(num[now] == x)
{
cnt[now]++;
push_up(now), push_up(f);
Splay(now);
return ;
}
f = now, now = son[now][x > num[now]];
if(!now)
{
num[++tot] = x, size[tot] = cnt[tot] = 1;
fa[tot] = f, son[f][x > num[f]] = tot;
push_up(f), Splay(tot);
return ;
}
}
}
}
int Find(int x)
{
int now = root, ans = 0;
while(true)
{
if(x < num[now])
{
now = son[now][0];
continue;
}
ans += size[son[now][0]];
if(num[now] == x)
{
Splay(now);
return ans + 1;
}
ans += cnt[now];
now = son[now][1];
}
}
int Kth(int rank)
{
int now = root;
while(1)
{
if(rank <= size[son[now][0]])
{
now = son[now][0];
continue;
}
rank -= size[son[now][0]];
if(rank <= cnt[now])
{
Splay(now);
return num[now];
}
rank -= cnt[now];
now = son[now][1];
}
}
int Pre()
{
int now = son[root][0];
while(son[now][1])
now = son[now][1];
return now;
}
int Suc()
{
int now = son[root][1];
while(son[now][0])
now = son[now][0];
return now;
}
void Delete(int x)
{
Find(x);
int now = root;
if(cnt[now] > 1) cnt[now]--, size[now]--;
else if(!son[now][0] && !son[now][1])
root = 0, clear(now);
else if(!son[now][0] && son[now][1])
fa[root = son[now][1]] = 0, clear(now);
else if(son[now][0] && !son[now][1])
fa[root = son[now][0]] = 0, clear(now);
else
{
int pre = Pre(), rt = root, rson = son[root][1];
Splay(pre), connect(rson, pre, 1);
clear(rt), push_up(root);
}
}
int main()
{
scanf("%d", &n);
for(int k = 1; k <= n; k++)
{
int opt, x;
scanf("%d %d", &opt, &x);
if(opt == 1)
Insert(x);
else if(opt == 2)
Delete(x);
else if(opt == 3)
printf("%d\n", Find(x));
else if(opt == 4)
printf("%d\n", Kth(x));
else if(opt == 5)
Insert(x), printf("%d\n", num[Pre()]), Delete(x);
else
Insert(x), printf("%d\n", num[Suc()]), Delete(x);
}
return 0;
}
$~\\$
$~\\$
$\quad\quad$ $Splay$ 不仅可以完成上面的 BST 共有操作，还可以维护序列，这也是它能成为 LCT 辅助树的原因之一。
$\quad\quad$ 首先，$Splay$ 有一个显然的性质：在不增加/删除节点的前提下，无论怎么旋转，$Splay$ 的本质都不会改变，其中序遍历也不会改变。
$\quad\quad$ 中序遍历的不变性是 $Splay$ 维护序列的基础，我们把原序列中各个数的位置和其在 $Splay$ 中的中序遍历序号依次对应，就可以完成由序列到 $Splay$ 的转换。
$\quad\quad$ 简单的说，就是：我们依次把序列中的数往 $Splay$ 最右侧的位置插（对应最大的中序遍历值），最后插出来的 $Splay$ 的中序遍历就是我们要的序列，且这个序列在进行 $Splay$ 操作后不会改变。
$\quad\quad$ （维护序列的 $Splay$ 实质其实是一棵以元素在序列中的位置为关键字的 BST）
$\quad\quad$ 下面，我们借助例题加以解释。
$\quad\quad$ 简单的说，本题要求维护一个支持区间翻转的序列。
$\quad\quad$ 为什么区间翻转可以用 $Splay$ 维护？
$\quad\quad$ 首先，我们可以简单的在 $Splay$ 中提取一个区间：把序列中第 $r+1$ 个点 $A$ 转到根，把序列中第 $l-1$ 个点 $B$ 转成根的左儿子，那么 $B$ 的右儿子对应的子树包含 $l-r$ 区间内的所有值。
$\quad\quad$ 为什么？我们前面提到了，这里的 $Splay$ 本质上是一棵以元素在序列中的位置为关键字的 BST，那么 $B$ 右子树中的所有节点在序列中的位置就应该大于 $l-1$，小于 $r+1$。
$\quad\quad$ 还有一个问题：我们怎么得到序列中第 $x$ 个点在 $Splay$ 中的编号？根据数组下标与中序遍历的对应原则，我们找 $Splay$ 中中序遍历为 $x$ 的点即可。（不知道怎么找？给个提示吧：我们之前找第 $K$ 小的数，本质上也是找中序遍历为 $x$ 的点）
$\quad\quad$ 好，我们把区间提取出来了，但怎么翻转呢？
$\quad\quad$ 很简单，交换子树中所有节点的左右儿子即可。
$\quad\quad$ 放图（在原序列中翻转区间$[2,4]$，点上的数值代表该项的权值）：
$\quad\quad$ 开始时：（中序遍历为1 2 3 4 5）
$\quad\quad$ 旋转节点1（B点），节点5（A点）。（不要忘了三点一线是特殊处理的）
$\quad\quad$ 我们发现，所有要翻转的点都在1点的右子树上，如下图…
$\quad\quad$ 交换左右儿子…（中序遍历为 1 4 3 2 5）
$~\\$
$\quad\quad$ 好了，翻完了…显然这个过程中可以打个懒惰标记…标记的打法类似线段树，记得每次向下前把标记打下来就行了。
$\quad\quad$ 至于最后输出时，中序遍历整个$Splay$即可。
$\quad\quad$ 另外，有一个小技巧：为了防止翻转时调用$l-1,r+1$越界，我们可以在开始时在左右两侧分别加入两个值。
$~\\$
- 代码：
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
inline int read();
//rev 为懒惰标记，没有比较记录点的权值
int son[N][2], fa[N], siz[N], rev[N];
int n, m, rt, tot;
//-----辅助函数-----//
//因为不删节点，就没必要有 clear 了
void connect(int x, int y, int z)
{
if(x) fa[x] = y;
if(y) son[y][z] = x;
}
void push_up(int x)
{
siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1;
}
//下放懒惰标记
void push_down(int x)
{
if(rev[x])
{
swap(son[x][0], son[x][1]);
rev[x] ^= 1, rev[son[x][0]] ^= 1, rev[son[x][1]] ^= 1;
}
}
int find(int x)
{
return x == son[fa[x]][1];
}
void rotate(int x)
{
int y = fa[x], z = fa[y], k = find(x), i = find(y);
connect(son[x][k ^ 1], y, k);
connect(y, x, k ^ 1);
connect(x, z, i);
push_up(y), push_up(x);
}
void Splay(int x, int to)
{
//一定是先从根节点，向下找到某个节点，再进行的 Splay
//所以 Splay 所在的点及其路径上的点一定是没有标记的
for(int f; (f = fa[x]) != to; rotate(x))
if(fa[f] != to) rotate(find(x) == find(f) ? f : x);
if(!to) rt = x;
}
//-----主要函数-----//
//插入建树，直接像线段树那样creat也可以
void Insert()
{
if(!rt)
{
siz[rt = ++tot] = 1;
return ;
}
//一路向右插就可以了
int now = rt, f = 0;
while(now)
f = now, now = son[now][1];
siz[now = ++tot] = 1, connect(now, f, 1);
Splay(now, 0);
}
//查询下标为 x 的数的编号
int Kth(int x)
{
int now = rt;
while(1)
{
//不要忘了下放标记
push_down(now);
if(x <= siz[son[now][0]])
{
now = son[now][0];
continue;
}
x -= siz[son[now][0]];
if(x == 1) return now;
x--, now = son[now][1];
}
}
//翻转某棵子树
void Reverse(int x)
{
rev[x] ^= 1;
}
//操作处理有点麻烦，单独拿出来处理
void work(int l, int r)
{
//找到需要翻的两个点
int L = Kth(l - 1), R = Kth(r + 1);
//把两个点翻到对应的位置上
Splay(R, 0), Splay(L, R);
//翻转已经提取出的整棵树
Reverse(son[L][1]);
}
//中序遍历输出
void Dfs(int x)
{
if(!x) return ;
//不要忘了下放标记
push_down(x);
Dfs(son[x][0]);
//别输出左右两个加进去的点了
if(x >= 2 && x <= n + 1)
printf("%d ", x - 1);
Dfs(son[x][1]);
}
signed main()
{
n = read(), m = read();
for(register int k = 1; k <= n + 2; k++)
Insert();
for(register int k = 1; k <= m; k++)
{
int l = read(), r = read();
//前面加了一个点，对应操作下标要加一
work(l + 1, r + 1);
}
Dfs(rt);
return 0;
}
inline int read()
{
int fh = 1, x = 0, ch = '~';
while(!(ch >= '0' && ch <= '9')) fh = ch == '-' ? -1 : 1, ch = getchar();
while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1), x += ch - '0', ch = getchar();
return x * fh;
}
$~\\$
结语：
$\quad\quad$ 最后是刷题表：
$\quad\quad$ 洛谷 P3165 [CQOI2014]排序机械臂（段维护板子）
$\quad\quad$ 洛谷 P2073 送花（极水的板子）
$\quad\quad$ 洛谷 P2343 宝石管理系统（更水的板子）
$\quad\quad$ 洛谷 P2286 [HNOI2004]宠物收养场 （有点麻烦…）
$\quad\quad$ 洛谷 P4146 序列终结者 （段维护板子$PLUS$）
$\quad\quad$ 洛谷 P2042 [NOI2005]维护数列 （超级码力）
$ $
$$\huge\color {#123456} \mathcal {E \ N \ D}$$
