splay

s p l a y splay splay 是一种平衡树，但是并不完全平衡。

它凭借一系列操作使得树趋近于平衡，所以与 A V L AVL AVL 比起来，时间可能没那么快，但是 s p l a y splay splay 可以应用到的地方很多，比如说区间翻转，这是 A V L AVL AVL 无法做到的。

并且LCT要用到splay。

规定 t r e e [ x ] . s o n [ 0 / 1 ] tree[x].son[0/1] tree[x].son[0/1] 表示 x x x 的左右儿子是谁。 t r e e [ x ] . s i z e tree[x].size tree[x].size 表示以 x x x 为根的子树大小。 t r e e [ x ] . f a tree[x].fa tree[x].fa 表示 x x x 的父亲节点。 原理 旋转

s p l a y splay splay 也是利用旋转来维护的，它旋转时传的是儿子节点，然后将儿子节点转到父亲节点。

旋转时有两种情况，一种是我是你的左儿子，一种是我是你的右儿子，但其实两种情况分析起来本质上都差不多，可以打在一起。（不用像 A V L AVL AVL 一样分开）

代码 int pdd(int x) { return tree[tree[x].fa].son[1] == x; }//x是它父亲的哪个儿子 void rotato(int x) { int y = tree[x].fa, z = tree[y].fa, p = pdd(x); tree[z].son[pdd(y)] = x; tree[x].fa = z, tree[y].fa = x; tree[y].son[p] = tree[x].son[p ^ 1], tree[tree[x].son[p ^ 1]].fa = y; tree[x].son[p ^ 1] = y; updata(y), updata(x);//更新信息 } splay

s p l a y splay splay 肯定有 s p l a y splay splay 操作。

s p l a y ( x , y ) splay(x, y) splay(x,y) 就是用来将 x x x 转成 y y y 的儿子。

用到了旋转操作。

代码 bool pd(int x, int y) { return tree[x].fa != y; } void splay(int x， int goal) { push(x);//因为有时候要区间翻转，这个用来用来下传翻转标记，如果题目没有翻转可以不用 for (int y; pd(x, goal); rotato(x)) { y = tree[x].fa; if (pd(y, goal))//用来加快程序速度，删除对程序正确性不会有任何影响 rotato(pdd(y) == pdd(x) ? y : x); } if (!goal) root = x; }

查找，删除的操作都可以参照AVL来做，所以不再叙述。（可以看看我的另一篇博客）

翻转

我们来看看翻转操作如何实现。

我们假设要将区间 l , r l, r l,r 翻转，我们设 l ′ , r ′ l',r' l′,r′ 分别为 l l l 位置的左边， r r r 位置的右边。

则我们可以先将 l l l 节点 s p l a y splay splay 到根节点，再将 r r r 节点 s p l a y splay splay 到根节点的右儿子。

此时 r r r 节点的左子树就是我们要翻转的区间。

由于平衡树的性质，我们只需要将该子树的每个节点的左右儿子交换，便可翻转整个区间。

此时我们前面的 s p l a y splay splay 中的 p u s h push push 就是用来将翻转标记翻转下来。

代码 void push(int x) { if (tree[x].fa) push(tree[x].fa); pushdown(x); } void reverse(int l, int r) { //此时的l,r就是l',r' splay(l, 0), splay(r, l), tree[tree[r].son[0]].flag ^= 1; }

此时 s p l a y splay splay 的基本操作就讲完了。