Splay

1. 平衡树
2. Splay
   1. AcWing 2437. Splay
   2. 旋转操作与伸展操作

Splay是算法竞赛最常用的平衡树之一。这种平衡树代码不长（相比红黑树），支持的操作较多。

平衡树

平衡树是特别的二叉搜索树。当数据较为刁钻时，二叉搜索树可能退化成单链，原本$O(logn)$的查找效率退化成$O(n)$。平衡树旨在通过特殊的插入/访问方式使得维护的二叉搜索树，使得搜索次数尽可能地小。

二叉搜索树的主要功能在于：中根遍历二叉搜索树，便利序列是有序的。平衡树对二叉搜索树进行的优化也需要满足：在优化后，树中根遍历的序列不能改变。

与AVL、Treap等平衡树相同，Splay通过“旋转”操作，在不改变中根遍历序列的前提下对原树进行变换。

Splay

一般来说，平衡树的优化思路都是设法使原树尽可能满，从而减小树的高度，进而查找效率。但Splay较为奇特，它的优化方式是每访问到一个点，都将其通过多次旋转（rotate）使其上升至根节点，之后再进行下一次访问。这在直观上非常符合缓存的局部性原理，但详细的证明较为复杂，此处不加赘述。总之，通过该种方式，查询/修改一个元素的时间复杂度总是$O(logn)$。

值得一提的是，将某结点通过多次旋转使其上升至另一节点下方的操作被称作“伸展（splay）”。

为方便说明，下面使用模版题讲解这种平衡树。

AcWing 2437. Splay

给定一个长度为 n 的整数序列，初始时序列为 1,2,…,n−1,n。

序列中的位置从左到右依次标号为 1∼n。

我们用[l,r] 来表示从位置 l 到位置 r 之间（包括两端点）的所有数字构成的子序列。

现在要对该序列进行 m 次操作，每次操作选定一个子序列[l,r]，并将该子序列中的所有数字进行翻转。

例如，对于现有序列 1 3 2 4 6 5 7，如果某次操作选定翻转子序列为[3,6]，那么经过这次操作后序列变为 1 3 5 6 4 2 7。

请求出经过 m 次操作后的序列。

回忆平衡树旋转（伸展）的性质：中根遍历的顺序总是不变。也就是说，对于每次操作给定的[l,r]，将l的前驱伸展至树的根节点，再将r的后驱伸展至根结点的右儿子。由于中根遍历序列不变，[l,r]之间的所有元素就都到l的左子树上了，并且，根结点的左子树中仅含有[l,r]之间的元素。根据中根遍历的性质，接下来只需要将根节点的左子树上所有兄弟都交换一下就行了，这一步骤可以再通过lazytag来优化。

需要注意的是，由于操作涉及各节点的前驱、后继，树上实际的节点应有n+2个。实际上，很多Splay的问题所给出的模型都需要考虑前驱和后继，处理的时候应格外谨慎。

旋转操作与伸展操作

上文笼统地提到，旋转操作可以在不改变树的中根遍历序列的情况下改变树的结构，通过多次旋转操作可以将点伸展至需要的地方。

首先看看旋转操作的代码

1
2
3
4
5
6
7
8
9
10

void rotate(int x)
{
    int y = tr[x].fa, z = tr[y].fa;
    int k = tr[y].son[1] == x;
    tr[z].son[tr[z].son[1] == y] = x, tr[x].p = z;
    tr[y].son[k] = tr[x].son[k ^ 1], tr[tr[x].son[k ^ 1]].p = y;
    tr[x].son[k ^ 1] = y, tr[y].p = x;
    tr[y].size = tr[tr[y].son[0]].size + tr[tr[y].son[1]].size;
    tr[x].size = tr[tr[x].son[0]].size + tr[tr[x].son[1]].size;
}

它的作用是：在保证树的中根遍历序列不变的情况下，让节点x所在的深度-1，即所谓“向上转。”

由于Splay总是需要将点伸展至根节点或者根节点的右儿子，完全没有向下转的必要，所以只需要向上转的操作。

一般来说，旋转分为左旋和右旋，由于只需要向上转，因此可以把所谓左旋右旋合在一起写。假设需要将x向上转，y是x的父节点，z是y的父节点（即x的爷节点），那么

• 如果x、y、z构成一条直链，以x为y左儿子，y为z左儿子为例：将x移到z的左儿子，将原先x的右儿子移到y的左儿子，再将y移到x的右儿子。（若x为y右儿子，y为z右儿子，则把上面描述的步骤左右颠倒即可）
• 如果x、y、z构成一条折链，以x为y右儿子，y为z左儿子为例：将x移到z的左儿子，将原先x的左儿子移到y的右儿子，再将y移到x的左儿子。（若x为y左儿子，y为z右儿子，则把上面描述的步骤左右颠倒即可）

不同的情况中可能存在大量重复操作，使用上述写法可以在很大程度上减少冗余。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

void rotate(int x)
{
    int y = tr[x].fa, z = tr[y].fa;
    int k = tr[y].son[1] == x; // x是/否是y的右儿子
    //将x移到原先y对应的z的儿子位
    tr[z].son[tr[z].son[1] == y] = x, tr[x].p = z;
    //若x原本为y左儿子，则将x的右儿子移到y的左儿子位；否则将x的左儿子移到y的右儿子位
    tr[y].son[k] = tr[x].son[k ^ 1], tr[tr[x].son[k ^ 1]].p = y;
    //若x原本为y左儿子，则将y移动到x的右儿子位；否则将y移动到x的左儿子位
    tr[x].son[k ^ 1] = y, tr[y].p = x;
    //更新x、y节点的子树大小
    tr[y].size = tr[tr[y].son[0]].size + tr[tr[y].son[1]].size;
    tr[x].size = tr[tr[x].son[0]].size + tr[tr[x].son[1]].size;
}

伸展操作就是一直向上转，进而将目标点送到目标位置。但“一直向上转”并不是“一直rotate(x)”，因为这样伸展完的树不够平衡，具体原因有严格证明，这里同样不加赘述。

正确的向上转的方法是：假设需要将x向上转，y是x的父节点，z是y的父节点（即x的爷节点），那么

• 如果x、y、z构成一条直链，则先rotate(y)，再rotate(x)
• 如果x、y、z构成一条折链，则执行两次rotate(x)