概述
伸展树（Splay）是二叉查找树的一种改进，所以和二叉查找树一样，Splay 也具有有序性。也就是说，对于 Splay 中的每一个节点 x，都满足其左树的每一个节点都小于 x，且左树的每一个节点都大于 x，也就是中序遍历的节点顺序不变。并且伸展树可以自我调整，方法就是下面的伸展操作。
伸展操作
概念
我们把 splay(r, x)（注意大小写）定义为把 Splay 中的第 x 个节点旋转至 r 处，但是要保证这个有序性。伸展操作分为三种情况。
- 节点
x的父节点y是根节点。这时如果x是左孩，那么就进行一次 Zig（右旋）操作；反之如果x是右孩，那么就进行一次 Zag（左旋）操作。其中 Zig 和 Zag 操作与 Treap 的左旋右旋操作一致。旋转后，x成为 Splay 的根节点。
- 节点
x的父节点y和y的父节点z在同一直线上。这时我们就按照实际情况进行一次 “Zig-Zig” 或 “Zag-Zag” 操作即可。
- 节点
x的父节点y和y的父节点z不在同一直线上。这时我们就按照实际情况进行一次 “Zig-Zag” 或 “Zag-Zig” 操作即可。
这就是 Splay 的三种旋转的方法。
实现
首先我们先定义一个 struct NODE：
注意事项：注意下面的
c{NULL, NULL}是 C++11 的语法，在竞赛中最好在{}中初始化，以免编译错误。
struct NODE {
NODE *c[2];
int value, _size;
NODE() : c{NULL, NULL}, value(0), _size(1) {}
int size(const int g) const { return c[g]? c[g]->_size : 0; }
};
伸展操作最重要的是：虽然上面的方法用到了一大堆父节点，但是不要把父节点和子节点混用，而且还用取地址符（&）（所谓混用，指混合用在旋转中），这样会导致一些很神奇的错误（& 的特性），这就是“垃圾代码制造器”的由来，惨痛的回忆……
不用父节点的话，我们就从根节点开始，应用分治的思想，一步一步往下找，然后再递归并（顺便）旋转。这样做的话，为了方便起见，我们在首位各加一个“哨兵”。
我们定义一个函数：splay(NODE *&p, int k)，作用为把第 k 个节点旋转至 p 处，并且修改调用它的指针（& 的特性）。
然后我们就要对第 k 个节点的位置进行分类讨论，我们就根据 p 的左树的节点数等来判断 k 处于哪个分支。
把上面的分类集合压缩一下，就可以得出以下代码。当然，rotate 的实现与 Treap 的实现完全一样。
void rotate(NODE *&p, const bool g) {
NODE *t = p->c[!g];
p->c[!g] = t->c[g];
t->c[g] = p;
maintain(p);
maintain(t);
p = t;
}
void splay(NODE *&p, int k) {
int s = p->size(0) + 1;
if (k < s) {
s = p->c[0]->size(0) + 1;
if (k < s) {
splay(p->c[0]->c[0], k);
rotate(p, 1);
}
else if (k > s) {
splay(p->c[0]->c[1], k - s);
rotate(p->c[0], 0);
}
rotate(p, 1);
}
else if (k > s) {
k -= s;
s = p->c[1]->size(0) + 1;
if (k < s) {
splay(p->c[1]->c[0], k);
rotate(p->c[1], 1);
}
else if(k > s) {
splay(p->c[1]->c[1], k - s);
rotate(p, 0);
}
rotate(p, 0);
}
}
基本操作
利用 Splay 的一些特性，可以进行一些修改、查询操作。
首先 Splay 可以随意调整一个节点到某个位置，时间复杂度不会很大（下面会证明）。并且随意旋转后 Splay 的中序遍历不变，也就是数列中每个数的相对位置不变。
这样的话，我们就快速地可以把任意一个区间提取出来。要提取区间 [l, r]，就可以把 l-1 旋转到根节点，再把 r+1 旋转至根节点的右孩子（边界需要按照实际情况进行调整）。
代码也很好写，就随便调用一下 splay 函数即可。
void extract(const int l, const int r) {
splay(root, l);
splay(root->c[1], r-root->size(0));
}
提取之后，根据中序遍历，该区间就位于以 root->c[1]->c[0] 为根的子树中，就可以很方便地进行插入、求和、删除、翻转等操作，非常灵活。
查询
查询一个区间，我们可以按上面的方法把这个区间提取出来，然后返回对应子树的信息即可。
int Query(const int l, const int r) {
extract(l, r+1);
return root->c[1]->sum(0); // 也可以返回其它信息
}
插入
插入操作既可以插入一棵子树，也可以插入一个节点，其本质都是相同的。一般来说，如果是插入多个数，我比较喜欢构造一棵 Splay 之后再插入进去（OO 的好处）。
注意事项：
&&也是 C++11 的语法之一，有移动的语义。在日常竞赛中，可以改为一个&，但也要注意传进来的 Splay 仍会移动进去（不保留原本）。
void Insert(const int pos, mSplay &&sp) {
extract(pos, pos);
root->c[1]->c[0] = sp.root;
sp.root = NULL;
maintain(root->c[1]);
maintain(root);
}
删除
删除操作也是要把对应的子树提取出来，然后整棵删除即可。
void remove(NODE *&p) {
if (!p) return;
remove(p->c[0]);
remove(p->c[1]);
delete p;
p = NULL;
}
void Delete(const int l, const int r) {
extract(l, r+1);
remove(root->c[1]->c[0]);
maintain(root->c[1]);
maintain(root);
}
翻转
区间翻转可谓是 Splay 最有特色的操作之一，非常的灵活。翻转一个区间 [l, r]，我们可以把这个区间提取出来，交换两个子节点，最后打一个 lazy 标记让下面的子树逐级翻转即可。
void pushdown(NODE *p) {
if (!p) return;
if (p->rotate) {
p->rotate = false;
swap(p->c[0], p->c[1]);
if (p->c[0]) p->c[0]->rotate ^= 1;
if (p->c[1]) p->c[1]->rotate ^= 1;
}
}
void Reverse(const int l, const int r) {
extract(l, r+1);
root->c[1]->c[0]->rotate ^= 1;
pushdown(root->c[1]->c[0]);
maintain(root->c[1]);
maintain(root);
}
对于其它区间修改操作，也可以像这样打一个 lazy 标记来处理。需要注意的是，要注意 pushdown 和 maintain 的时机，不要在 pushdown 后又用 maintain 右修改回去了（笑）。
整合代码
上面的代码都是精心设计过的（雾），可以较好地协调工作。如果需要的话，也可以把上面的代码放进一个 class 中（这就是上面 mSplay 的由来），其中大写开头的都是导出函数，剩下的都可以置为 private，是不是封装地很好呢（雾）。
使用 OOP（面向对象）设计思想可以在一定程度上使程序变得简单易懂易用（像 vector 等一样），并且充满了浓浓的 C++ 气息（雾）。
毒瘤例题
题目：[NOI2005] 维护数列
链接：洛谷
正解（雾）：R7500133
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：伸展树 Splay”