平衡树再总结
平衡树，二叉查找树的改进版，可以做各种奇怪的操作。
Splay
又称伸展树。有两种写法：递归版（无需维护父指针）、非递归版（维护父指针版本）。在区间维护操作、信息和 LCT 上有广泛的应用。
Splay 的核心操作为splay(x)，即将点 x 旋转到根。依赖于 Rotate，Splay 有两种版本：双旋和单旋（Spaly）。在特殊构造下的数据 Spaly 可以被卡掉。
区间的旋转操作
维护一个 lazy。由于区间是中序遍历得到的结果，翻转后的区间是中序遍历全部翻转过后的结果，因此只需记录懒标记，在需要访问儿子的地方前设置 pushdown 即可。
递归版
Rotate(&x, d):
维护 x 的被引用状态，需要向 Rotate 传递方向参数。作用是将 x 的儿子旋到 x 处。
void rot(Node *&x, int d) {
Node *y=x->ch[d]; y->pud();
x->ch[d]=y->ch[!d], y->ch[!d]=x;
x->upd(), y->upd(), x=y;
}Splay(&x, k):
Splay 过程将 Find 和 Splay 进行合并。查找到结点之后直接进行旋转。k 是需要查找的键值，x 需要维护引用状态。
void splay(Node *&x, int k) {
x->pud();
int d=x->cmp(k);
if(d!=-1 && x->ch[d]!=nil) {
x->ch[d]->pud();
int d2=x->ch[d]->cmp(k);
if(d2!=-1 && x->ch[d]->ch[d2]!=nil) {
splay(x->ch[d]->ch[d2], k);
if(d==d2) rot(x, d), rot(x, d);
else rot(x->ch[d], d2), rot(x, d);
}
else rot(x, d);
}
}非递归版
在需要维护特定结点地址并将其旋到根节点的时候，需要同时维护父指针和非递归版 splay。
如果需要 Find 的话，效率往往比非递归版要低。
结构体的成员函数
dir()
如果父指针为 nil，返回 -1，否则返回父指针的对应儿子方向。
nroot()
如果不在根处，返回 1，否则返回 0. 常见于 LCT 中的 splay。
Rotate(x)
作用是将 x 向上旋一格。由于 y,z 是直接计算，因此只算一个参。
需要注意指针指向 nil 的情况。
（假设 x 是 y 的右子树）顺序是先将 x 的左子树接到 y 的右子树，更新 x 的左子树的父指针。
然后再更新 x 的父指针和 x 的新的父节点的儿子（这里需要用到还没被更改的 y）。
最后再将 y 接到 x 的左子树，更新 y 的父指针。
此时一般只需要更新 y 从儿子更新上来的信息（因为只有 y 的儿子发生了变化），然后在 splay 完之后再更新 x 的信息。
void rot(Node *x) {
Node *y=x->f, *z=y->f;
int d=x->dir();
y->ch[d]=x->ch[!d];
if(x->ch[!d]!=nil) x->ch[!d]->f=y;
x->f=z;
if(y->dir()!=-1) z->ch[y->dir()]=x;
x->ch[!d]=y, y->f=x, y->upd();
}Splay(x)
若要区间翻转，一般选择先用栈将点到根的结点全部下放后再进行处理。
Node *stk[N];
void splay(Node *x, Node *f) {
int z=0;
Node *y=x;
stk[++z]=y;
while(y->f!=f) stk[++z]=y=y->f;
while(z) stk[z--]->pud();
while(x->f!=f) {
y=x->f;
if(y->f==f) rot(x);
else if(y->dir() == x->dir()) rot(y), rot(x);
else rot(x), rot(x);
}
x->upd();
if(f==nil) rt=x;
}