Splay 学习笔记
前面的瞎BB
我很喜欢 Splay，虽然其中有一部分因素来源于对 Tarjan 老爷爷的崇拜（bushi
不过一想到 LCT 和 Splay 都是 Tarjan 和另外一位大佬发明的，就有种 Splay 为了 LCT 而生的错觉（bushi
在学习之前建议先了解 BST 和平衡树的概念当初我没看这两玩意直接冲Splay看得头大
而且，我觉得如果你真的理解了 splay 这个操作，其实 Splay 写起来是真的不要脑子，但是很多板子都有着相当多的乱七八糟的分类讨论（让我头大）……
关于 Splay
其实 Splay 只有一个核心函数：旋转到根。
rotate
先讲一下旋转。旋转函数实质上就是将当前节点 $p$ 的父亲变为其儿子，同时此过程依旧要维护 BST 的性质。如下图：
这种情况，我认为 旋转 这个词其实并不贴切，因为如果你用 旋转 去形容它的话不那么直观，我更愿意将其称作 上移 ——将当前节点移到它的父亲上面，同时满足 BST 的性质。（但是旋转念顺口了啊喂qwq）
接下来我们做个分类讨论：
-
如果当前节点(p)是其父亲节点(fa)的左儿子：
为了保证 BST 的性质，那么在旋转过后 fa 将变成 p 的右儿子，而 p 原本的右儿子将会变成 fa 的左儿子。 -
如果当前节点(p)是其父亲节点(fa)的右儿子：
那么旋转过后 fa 将会变成 p 的左儿子，而 p 原本的左儿子将会变成 fa 的右儿子。
此处建议大家手玩一下这个旋转操作，就会发现，所谓的 旋转，其实本质上就是将当前节点 p 上移以后重新处理和其儿子、父亲的连边。
指针实现：
struct node {
node *son[2], *fa;
};
// 对于一个节点 *p, p->son[0] 为它的左儿子，p->son[1] 为它的右儿子
int get(node *p) {
if (p->fa->son[0] == p) return 0;
return 1;
}
// 可简写成: return p->fa->son[1] == son;
// 将 fa 和 son 重新连边，并且 son 是 fa 的左/右子树
void connect(node *fa, node *son, int d) {
if (fa != nullptr) fa->son[d] = son;
if (son != nullptr) son->fa = fa;
}
// 重新维护 p，这个重新维护其实和线段树里的 pushup 本质上是一样的
void maintain(node *p) {
if (p == nullptr) return;
// ...
}
void rotate(node *p) {
node *fa = p->fa, *grand = fa->fa;
int d = get(p), fd = get(fa);
connect(fa, p->son[d ^ 1], d); // p 的 d ^ 1 儿子将会变成 fa，所以这个儿子必须被 fa 所管理
connect(p, fa, d ^ 1); // fa会变成 p 的与 d 刚好相反的儿子
connect(grand, p, fd); // 无论 p 和 fa 怎么玩，它们相对 grand 的子树将始终不变
// 在一次旋转过程中，将会影响三个节点：fa，p，grand
// 同时在旋转之后从下往上的顺序也是fa, p, grand，所以维护先后顺序也要注意。
maintain(fa), maintain(p), maintain(grand);
}
数组实现：
const int kMaxN = 1e6;
struct node {
int son[2], fa;
}a[kMaxN];
int get(int p) {
return a[a[p].fa].son[1] == p;
}
void connect(int fa, int son, int d) {
if (fa) a[fa].son[d] = son;
if (son) a[son].fa = fa;
}
void maintain(int p) {
// ...
}
void rotate(int p) {
itn fa = a[p].fa, grand = a[fa].fa;
int d = get(p), fd = get(fa);
connect(fa, a[p].son[d ^ 1], d);
connect(p, fa, d ^ 1);
connect(gradn, p, fd);
maintain(fa), maintain(p), maintain(grand);
}
这份代码中 rotate 用 connect 避免了对空指针的特殊考虑，将空指针的特殊情况由 connect 统一管理。这么写会让代码更加直观一些。
等会啊，rotate 有个啥用呢？它也不能保证旋转某个节点后树一定是平衡的啊。如下图(节点旁数字代表高度)：
这本来是一个很平衡的状态，然后我们轻轻地将 2 旋转一下：
完犊子嘞！以 2 为根的两个子树并不能保证平衡。也就是说，你可以通过各种稀奇古怪的操作使两个子树的高度差越来越大、越来越大……最后甚至可能退化成一个链（当然也许没这么恐怖但是大差不差了）
如果我们不进行场景而直接使用旋转乱搞的话，很容易导致 BST 不再平衡然后被各种毒瘤出题人卡飞
splay
Splay 独有的伸展操作/splay操作就是为了解决这个问题而诞生的。
首先 splay 强制要求你每次访问一个节点之后要将其旋转至根节点。没事也就只是多个常数而已（所以Splay常数大XD）。同时在 Splay 操作中维护 p 到根节点上的点使其能够保持平衡。
首先分三种情况讨论：
- 父亲节点就是根节点。没什么好说的直接移就完事。
- 当前节点、父亲节点、祖先节点共线：
这种情况下，先旋转父亲节点再旋转当前节点。 - 当前节点、父亲节点、祖先节点不共线：
这种情况下，直接旋转两遍当前节点。
啊，你问我为啥这样子整体会更平衡？
巧了我也不会证，但是oi-wiki上有
但是不可否认的是它确实将时间复杂度压了下来，并且均摊成了 $\log n$
指针实现：
void splay(node *p) {
while (1) {
if (p->fa == root) {
rotate(p);
break;
}
if (get(p->fa) == get(p)) {
rotate(p->fa);
rotate(p);
} else {
rotate(p);
rotate(p);
}
}
root = p;
}
数组实现：
void splay(int p) {
while (1) {
if (a[p].fa == root) {
rotate(p);
break;
}
if (get(a[p].fa) == get(p)) {
rotate(a[p].fa);
rotate(p);
} else {
rotate(p);
rotate(p);
}
}
}
看上去很难看，有一个更简洁的写法：
指针实现：
void splay(node *p) {
for (node *fa; (fa = p->fa) != nullptr; rotate(p)) {
if (fa->fa != nullptr) {
rotate(get(p) == get(fa) ? fa : p);
}
}
root = p;
}
数组实现：
void splay(int p) {
for (int fa; (fa = a[p].fa) != 0; rotate(p)) {
if (a[fa].fa != 0) {
rotate(get(p) == get(fa) ? fa : p);
}
}
root = p;
}
很显然，根节点是没有父亲的。如果一个节点没有父亲，那么我便可以认为它已经成为了根节点。
基于这个思路，我们还可以将 splay 操作拓展理解为：将某个节点不断旋转，直到它的父亲成为了另外一个节点。如果它的父亲指针为空，那么等价于它会移到根节点。
指针实现：
void splay(node *p, node *top) {
for (node *fa; (fa = p->fa) != top; rotate(p)) {
if (fa->fa != top) {
rotate(get(p) == get(fa) ? fa : p);
}
}
if (top == nullptr) root = p;
}
数组实现：
void splay(int p, int top) {
for (int fa; (fa = p->fa) != top; rotate(p)) {
if (a[fa].fa != top) {
rotate(get(p) == get(fa) ? fa : p);
}
}
if (top == 0) root = p;
}
一些代码细节
哨兵节点
烧饼节点
哨兵节点仅仅只是一种占位节点。它通常表示为无穷大或者无穷小。
在上图，我们设定了两个哨兵节点代表无穷大和无穷小。我们并不关系它们是否有具体取值，但是在 BST 中它的键值就是无穷大和无穷小。
可以根据情况来选择写一个或两个哨兵节点。但是无论如何，哨兵节点是一定要写的，这样可以减少许多的分类讨论（如插入节点是不需要再判断树是否为空）。
用一个节点代替空指针
如果你是用数组实现的 Splay，那么这里可以跳过。
如果你用指针写，那么多少会遇到在 maintain 等环节需要考虑子树是否为空的苦恼，当访问到空指针也确实是一件比较难调的事情。
我们可以自己定义一个指针 nil，在默认情况下它将是所有节点的儿子节点、父亲节点：
nil 自己的左右儿子和父亲将永远是自己，它不会指向其它节点只有其它节点会指向它。
nil 不是必须的，它的唯一作用就是代替空指针，并且可以为它赋上一定的值，这样讲减少很多情况下针对空指针的分类讨论。
具体操作
kth、查询前驱后继
BST 的基础操作，自己去搞。
不过记得找到之后把它 splay 到根
插入
假如我要往节点 p 后插入一个节点。
先把 p 旋转到根
然后直接插入就完事了
p 原本的右子树就接到 new 上面去了。
插入序列/Splay合并
如果我们要往 p 后插入一个序列，和上面插入节点操作一样，先将 p 旋转到根，然后把需要插入的序列构造成一个平衡树。
有两个插入的方法：
-
直接插入：
操作完之后最好再把 8 号节点 splay 一遍，这样可以维护好它到根节点所有节点的信息。 -
查询后继后插入：
这么做有一个问题：如果我没有后继怎么？所以上文中提到了无穷大的哨兵节点就是这么用的，它保证了一定会有后继。
首先将 p 的后继直接旋转到 p 下面来。
suffix 是一定没有左子树的，基于 BST 的性质，接下来可以直接把要插入的序列插入进去
维护好 suffix 和 p 的信息就完了。
基于这个思路，若Splay维护的序列上的信息你也可以用这种方式快速合并（不过要把哨兵节点去掉）
当然，如果你是将两个按照键值排序的Splay合并……老老实实写启发式合并吧。
操作连续子序列/Splay分裂
其实Splay也是可以处理分裂的，只是不用分裂合并维护平衡罢了。
如果我们想要操作一个区间，一个合理的方式是将这个区间内的节点全部独立到一颗子树里，如下图：
虽然看上去并不好看，但是确实达成了我们的要求。将我们需要操作的节点都独立到了一个子树里。这样我们做区间修改还是区间查询时，只需要对这个子树的根节点进行操作就可以了。
假设我们要独立一个区间 l, r，那么只需要把 l - 1 和 r + 1 （下面称呼为前驱和后继）的节点通过 splay 操作向上旋转即可。我常做的方法是将前驱旋转至根、将后继旋转至前驱下，如下图：
由于我们并不会破坏 BST 的性质，旋转后的后继的左子树，一定是 l, r 对应的子树。
也许你会有疑问：第一个节点没有前驱、最后一个点没有后继。如果你使用了哨兵节点来代表无穷小和无穷大，这个问题就可以避免，减少分类讨论的必要。
利用将子树独立出来的方式，可以将一个 Splay 分裂成两个 Splay，具体实现应该很显然。
删除
依旧用上面的树为例子：
直接将要删除的区间独立出来，然后可以方便删除。
板子
这里只给出了最基础最基础的板子，没有任何实际功能。
class Splay {
struct node {
node *son[2] = {nullptr, nullptr}, *fa = nullptr;
} *root;
int get(node *p) {
return p->fa->son[1] == p;
}
void connect(node *fa, node *son, int d) {
if (fa != nullptr) fa->son[d] = son;
if (son != nullptr) son->fa = fa;
}
void maintain(node *p) {}
void rotate(node *p) {
int d = get(p), fd = get(p->fa);
node *fa = p->fa, *grand = fa->fa;
connect(p->fa, p->son[d ^ 1], d);
connect(p, fa, d ^ 1);
connect(grand, p, fd);
maintain(fa), maintain(p), maintain(grand);
}
void splay(node *p, node *top = nullptr) {
for (node *fa; (fa = p->fa) != top; rotate(p)) {
if (fa->fa != top) rotate(get(p) == get(fa) ? fa : p);
}
if (top == nullptr) root = p;
}
public:
};
数组实现：
你问这个啊？懒得写了自己写去吧qwq
我觉得我写的还是挺详细的，然后所有的内容自己去补充吧……
标签：node,学习,rotate,get,笔记,son,Splay,fa,节点 From： https://www.cnblogs.com/ycsblogs/p/17228124.html