Splay

# Splay 树 ## 定义 Splay 树是一个二叉**平衡**搜索树，它可以通过 **Splay 操作** 将一个结点旋转至根结点或者一个给定的结点的下一层，使得整棵树仍然满足二叉搜索树的性质。 Splay 树可以在均摊 $O(\log n)$ 的时间内完成查找、插入、查询、删除等操作。 > **二叉搜索树**的定义： > > - 空树是一个二叉搜索树； > - 根结点左子树中的结点权值均小于根结点的权值； > - 根结点右子树中的结点权值均大于根结点的权值； > - 根结点的左右子树均为二叉搜索树。 ## 结构 在 Splay 中，一共需要维护如下信息： - `root`：树的根结点编号。 - `tot`：当前总共开了点的个数（Splay 树显然使用动态开点）。 - `fa[i]`：结点 $i$ 的父亲结点。 - `son[i][0/1]`：结点 $i$ 的左右儿子编号，左儿子为 `son[i][0]`，右儿子为 `son[i][1]`。 - `val[i]`：结点 $i$ 的权值。 - `cnt[i]`：权值为 `val[i]` 的数字的出现个数。 - `siz[i]`：结点 $i$ 及其子树的大小。 ## 基本操作 ### 辅助函数 - `pushup(x)`：合并左右儿子的信息（即大小），更新至当前结点。 - `get(x)`：返回 $0$ 表示 $x$ 是父结点的左儿子，返回 $1$ 表示 $x$ 是父结点的右儿子。 - `clear(x)`：销毁结点 $x$，即将一切信息清零。 ```cpp void pushup(int x) { // 合并 x 的左儿子与右儿子，得到 x 的大小 siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x]; } bool get(int x) { // get(x)=1 说明 x 是右儿子，反之是左儿子 return x == son[fa[x]][1]; } void clear(int x) { // 销毁结点 x son[x][0] = son[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0; } ``` ### 旋转  > 左旋是右旋的**逆操作**，所以下面只讨论右旋。 旋转操作如上图。 可以发现，右旋是把 $x$ 提到 $z$ 的下面然后把 $y$ 压下去，此时由于 $x$ 有有儿子了，所以如图可以想象成 $B$ 不动，此时就接到了 $y$ 的下面（胡思乱想中）。 ~~实际把图片记住就行了，上面扯一大通 P 用没有~~ --- 在右旋中，我们需要知道 $x$ 的父亲结点和爷爷结点，所以 ```cpp int y = fa[x], z = fa[y]; ``` 然后我们还需要知道 $x$ 是 $y$ 的左儿子还是右儿子，如果 $x$ 是左儿子就右旋，反之左旋。 ```cpp int id = get(x); // 判断 x 是 y 的左儿子还是右儿子 ``` 容易发现，在右旋中，改变的边的关系只有 $x-z$，$x-y$，$y-B$，所以我们分别考虑。 #### 修改为 $x-z$ 由于 $x$ 替换掉的是 $y$ 的位置，所以需要先知道 $y$ 是 $z$ 的哪个儿子，故先 `get(y)`。 当 $z$ 点不存在时（即 $z=0$），那么更新 `son[z]` 会发生错误，因为访问的时候一般是用是否为 $0$ 判断点是否存在。若 $z$ 为根结点，那么就会遍历下去导致错误的答案。 而 $x$ 必然存在，无需判断。 ```cpp if (z) son[z][get(y)] = x; fa[x] = z; ``` #### 修改为 $x-y$ 由于右旋保证了 $y$ 是存在的，所以两种情况都无需判断。 ```cpp son[x][id ^ 1] = y, fa[y] = x; ``` #### 修改为 $y-B$ $B$ 是 $x$ 的右儿子，而 $x$ 是 $y$ 的左儿子，所以发现 $B$ 就是 `son[x][id ^ 1]`。 同理此时 $B$ 不一定存在，所以也需要判断。 ```cpp son[y][id] = son[x][id ^ 1]; if (son[x][id ^ 1]) fa[son[x][id ^ 1]] = y; ``` #### 完整代码 ```cpp void rotate(int x) { int y = fa[x], z = fa[y]; int id = get(x); // 判断 x 是 y 的左儿子还是右儿子 if (z) son[z][get(y)] = x; fa[x] = z; son[y][id] = son[x][id ^ 1]; if (son[x][id ^ 1]) fa[son[x][id ^ 1]] = y; son[x][id ^ 1] = y, fa[y] = x; pushup(y), pushup(x); } ``` ### Splay 操作 Splay 操作规定：每操作（包括但不限于插入、删除，详见代码）一个结点 $x$ 后，都要将这个节点 $x$ 旋转为结点 $k$ 的儿子，若 $k=0$ 则将其旋转至根结点。 --- 根据定义，当 `fa[x] != k` 时，需要一直向上旋转，故写一个 `while` 循环。 #### 特殊型  如图，$k$ 是 $x$ 的爷爷结点，此情况称为**特殊型**。 对于这两种情况，我们只需要将 $x$ 点分别左旋、右旋，就可以让 $x$ 顶替掉 $y$ 的位置，成为 $k$ 的儿子。 #### 同构型  如图，当 $x$ 的爷爷节点非 $k$，且 $x,y,k$ 三点共线时，此情况称为**同构型**。 此时我们的目标是让 $x$ 顶替掉 $z$​，成为这一条链中深度最浅的链头。 ---  首先，我们将 $y$ 点旋转，此时 $y$ 成为深度最浅的结点，同时 $x,z$ 是 $y$ 的两个儿子。 ---  然后我们将 $x$ 点旋转，让 $x$ 成为 $y$ 的父亲，此时 $x$ 就成为了深度最浅的点，操作完成。 --- **总结**：对于同构型，先旋转 $y$，再旋转 $x$。 #### 异构型  如图，当 $x$ 的爷爷结点非 $k$，且 $x,y,z$​ 三点构成折线时，此情况称为**异构型**。 此时我们的目标同样是让 $x$ 顶替掉 $z$，成为这一条链中深度最浅的链头。 ---  首先，我们将 $x$ 点旋转，此时 $x$ 称为 $z$ 的儿子，三点共线。 ---  然后我们再次将 $x$ 点旋转， $z$ 称为 $x$ 的儿子，此时 $x$​ 就成为了深度最浅的点，操作完成。 --- **总结**：对于异构型，先旋转 $x$，再旋转 $x$​。 #### 代码实现 发现无论对于哪种情况，最后都会旋转一次 $x$，所以可以将这一次操作提取出来。 如何判断三点是同构还是异构呢？可以用 $\text{get}(x)\oplus\text{get}(y)$​ 获得。 具体实现详见代码。 > ##### 判断同构、异构的解释 > > - 同构 > > 此时 $x$ 是 $y$ 的左（右）儿子，$y$ 是 $z$ 的左（右）儿子，儿子左右情况相同，那么 $\text{get}(x)=\text{get}(y)$，异或值为 $0$。 > > - 异构 > > 此时 $x$ 是 $y$ 的左（右）儿子，$y$ 是 $z$ 的右（左）儿子，儿子左右情况不同，那么 $\text{get}(x)\not=\text{get}(y)$，且一个为 $0$ 一个为 $1$，故异或值为 $1$。 ```cpp void splay(int x, int k) { // 将 x 转到 k 的下面 while (fa[x] != k) { int y = fa[x], z = fa[y]; if (z != k) { if (get(x) ^ get(y)) rotate(x); // 异构 else rotate(y); // 同构 } rotate(x); } if (!k) root = x;// 若旋转为根结点，那么将根结点 root 设为 x } ``` ## 时间复杂度分析 > 本部分来自 OI-wiki。 考虑对 Splay 操作中的三种情况分析复杂度。采用势能分析，定义一个 $n$ 个节点的 Splay 树进行了 $m$ 次 Splay 操作。 可记 $w(x)=\left\lfloor\log\text{size}_x\right\rfloor$，定义势能函数为 $\varphi=\sum w(x)$，其中 $\varphi(0)\le n\log n$。 在第 $i$ 次操作后势能为 $\varphi(i)$​，则我们只需求出初始势能和每次的势能变化量的和即可。 - **特殊型**：势能变化量为 $$ \begin{aligned} &1+w'(x)+w'(y)-w(x)-w(y)\\ \le\,&1+w'(y)-w(x)\\ \le\,&1+w'(x)-w(x) \end{aligned} $$ - **同构型**：势能变化量为 $$ \begin{aligned} &1+w'(x)+w'(y)+w'(z)-w(x)-w(y)-w(z)\\ \le\,& 1+w'(y)+w'(z)-w(x)-w(y)\\ \le\,& 1+w'(x)+w'(z)-2w(x)\\ \le\,& 3\big(w'(x)-w(x)\big) \end{aligned} $$ - **异构型**：势能变化量为 $$ \begin{aligned} &1+w'(x)+w'(y)+w'(z)-w(x)-w(y)-w(z)\\ \le\,& 1+w'(y)+w'(z)-w(x)-w(y)\\ \le\,& 1+w'(z)+w'(y)-2w(x)\\ \le\,& 2w'(x)-w'(z)-w'(y)+w'(z)-w(x)-w(y)\\ \le\,& 2\big(w'(x)-w(x)\big) \end{aligned} $$ 由此可见，三种操作的势能全部可以缩放为 $\le 3\big(w'(x)-w(x)\big)$。 令 $w^{(n)}(x)=w'^{(n-1)(x)}$，$w^{(0)}(x)=w(x)$，Splay 操作一次依次访问了 $x_1,x_2,\cdots,x_n$，最终 $x_1$ 成为深度最浅的结点，那么可得： $$ \begin{aligned} 3\left(\sum\limits_{i=0}^{n-2}\left(w^{(i+1)}(x_1)-w^{(i)}(x_1)\right)+w(n)-w^{(n-1)}(x_1)\right)+1&=3\big(w(n)-w(x_1)\big)+1\\ &\le \log n \end{aligned} $$ 继而可得： $$ \sum\limits_{i=1}^{m}\big(\varphi(m-i+1)-\varphi(m-i)\big)+\varphi(0)=n\log n+m\log n $$ 因此，对于 $n$ 个结点的 Splay 树，做一次 Splay 操作的均摊复杂度为 $O(\log n)$。 因此基于 Splay 的操作的时间复杂度也是均摊 $O(\log n)$ 的。 ## 应用 1：维护一个集合 例题：[#104. 普通平衡树 - 题目 - LibreOJ (loj.ac)](https://loj.ac/p/104) ### 插入 由于二叉搜索是递归定义的，所以可以用递归的思想考虑（假设插入值为 $k$）： - 如果当前结点为空，那么就新建一个结点存储当前值。 - 如果当前结点的权值等于 $k$，那么更新当前结点的计数器并且更新当前结点与父亲的大小。 - 若 $k$ 小于权值就进入左子树，大于权值就进入右子树。 **注意，最后更新/新建结点之后，必须执行 Splay 操作，否则时间复杂度不正确！** ```cpp void insert(int k) { if (!root) { // 树为空，新建节点 val[++tot] = k; ++cnt[tot]; root = tot; pushup(root); // 更新大小 return ; } int x = root, y = 0; while (true) { if (val[x] == k) { // 找到目标 ++cnt[x]; // 更新计数器 pushup(x), pushup(y); splay(x, 0); // 旋转至根结点 break; } y = x, x = son[x][val[x] < k]; // 进入子树 if (!x) { // 到了空结点，插入新结点 val[++tot] = k; ++cnt[tot]; fa[tot] = y; son[y][val[y] < k] = tot; // 根据二叉搜索树的性质插入 pushup(tot); pushup(y); splay(tot, 0); break; } } ``` ### 根据权值查询排名 假设当前给定的权值为 $k$，要查找 $k$​ 的排名。 维护一个 $\text{res}$ 统计当前已经计算了权值小于 $k$ 的结点个数。 - 当前结点为空，返回 $\text{res}+1$。 - $k$ 小于当前结点的权值，那么进入当前结点的左子树查找，无需更新 $\text{res}$。 - $k$​ 大于等于当前结点的权值 那么当前结点的左子树中的结点都小于 $k$，`res += siz[son[x][0]]`，加上左子树的大小。 如果 $k$ 等于当前结点的权值，那么将其旋转至根结点，返回 $\text{res}+1$。 如果 $k$ 大于当前结点的权值，那么当前结点的权值也小于 $k$ 了，`res += cnt[x]`，同时进入右子树。 ```cpp int get_rank(int k) { // 查询 k 的排名 int res = 0, x = root; while (true) { if (k < val[x]) x = son[x][0]; // k 落在 x 的左子树 else { res += siz[son[x][0]]; // 加上左子树的大小 if (!x) return res + 1; // 当前结点为空 if (val[x] == k) return splay(x, 0), res + 1; // 当前结点权值等于 k res += cnt[x], x = son[x][1]; // 进入右子树 } } return -1; } ``` ### 根据排名查询权值 假设当前要查询排名为 $k$​ 的数，但是在下面，$k$ 是实时维护的。 - 如果 `k <= siz[son[x][0]]`，那么排名为 $k$ 的数就在左子树中，进入左子树即可。 - 否则让 `k -= cnt[x] + siz[son[x][0]]`，相当于减去根结点的数量和左子树大小。 - 如果此时 $k\le 0$，那么说明 `siz[son[x][0]] < k <= cnt[x]`，即排名为 $k$ 的数就是当前结点。将其旋转至跟节点后返回即可。 - 否则进入右子树。 ```cpp int get_kth(int k) { // 查询排名为 k 的数 int x = root; while (true) { if (son[x][0] && k <= siz[son[x][0]]) x = son[x][0]; // 进入左子树 else { k -= cnt[x] + siz[son[x][0]]; // 减去根结点的数量和左子树大小 if (k <= 0) return splay(x, 0), val[x]; // 说明 siz[son[x][0]] < k <= cnt[x] x = son[x][1]; // 进入右子树 } } return -1; // 找不到，即树的大小 < k } ``` ### 查询根结点的前驱/后继 > 至于为什么要查询根结点的前驱/后继，将会在后面的操作中给出解释。 > > 如果想要查找一个任意权值 $k$ 的前驱/后继，只需先将 $k$ 插入树中。 > > 由于插入函数中执行了 splay，所以此时 $k$​​ 就位于根结点的位置，可以直接调用函数。 > > 查询完之后删除 $k$ 即可。 由于前驱是小于根结点权值的最大的数，所以只要先进入左子树，然后一直向右找即可。 后继同理。 注意，下面代码返回的是结点编号，所以在最后输出的时候要套一层 `val[]`。 ```cpp int get_pre() { // 查询根节点的前驱 int x = son[root][0]; // 进入左子树 while (son[x][1]) x = son[x][1]; // 一直往右找 splay(x, 0); // 旋转至根结点 return x; } int get_nxt() { // 查询根节点的后继 int x = son[root][1]; // 进入右子树 while (son[x][0]) x = son[x][0]; // 一直往左找 splay(x, 0); // 旋转至根结点 return x; } ``` ### 合并两颗 Splay 树 设两棵树的根结点分别为 $x,y$，那么要求 $x$ 树中的最大值小于 $y$ 树中的最小值。 - 若 $x=\varnothing$ 或 $y=\varnothing$，那么返回非空的树或者空树。 - 否则将 $x$ 树中最大值 splay 至根结点，然后将其右子树设为 $y$。这样就保证了二叉搜索树的性质。 这只是一个辅助删除结点的思想，并不需要具体实现为一个函数。 ### 删除一个结点 假设要删除一个权值为 $k$ 的数。 > 如果要将权值为 $k$ 的数，那么直接将计数器置为 $0$ 即可。 首先将 $x$ 旋转到根结点。 - 若 `cnt[x] > 1`，那么 `--cnt[x]` 并返回。 - 否则删除根结点，并合并左右子树。 思路听起来很简单，但是实现起来有一定的理解难度。 ```cpp void erase(int k) { // 删除一个权值为 k 的数 get_rank(k); // 因为只知道权值为 k，那么可以用查找 k 的排名函数找到权值为 k 的结点并将其旋转至根结点 if (cnt[root] > 1) { // 直接删除一个数 --cnt[root]; pushup(root); // 更新大小 return ; } if (!son[root][0] && !son[root][1]) { // 树中只有一个根结点 clear(root); // 清空根结点 root = 0; // 根结点置为 0 return ; } if (!son[root][0]) { // 左子树为空 int cur = root; root = son[root][1]; // 将根结点设为右子树的根结点 fa[root] = 0; // 将父亲设为空 clear(cur); // 清除原来的根结点 return ; } if (!son[root][1]) { // 右子树为空 int cur = root; // 将根结点设为左子树的根结点 fa[root = son[root][0]] = 0; clear(cur); return ; } /* 由于原树分裂成了左右子树，而左子树的最大值必然小于右子树的最小值，那么左子树为 x，右子树为 y。 x = get_pre() 得到了 x 中的最大值，并同时通过 splay 操作将其旋转至整棵树的根结点。 此时将原树的右儿子的父亲设为当前根结点，并且更新儿子关系。 最后清除原根节点，并且更新根结点大小。 */ int cur = root, x = get_pre(); fa[son[cur][1]] = x; son[x][1] = son[cur][1]; clear(cur); pushup(root); } ``` ### 完整代码 其中 $N$ 为最大的总共开的点的数量，如果不确定可以用 `std::vector` 代替。 ```cpp struct Splay { int root, tot, val[N], siz[N], cnt[N], fa[N], son[N][2]; void pushup(int x) { // 合并 x 的左儿子与右儿子，得到 x 的大小 siz[x] = siz[son[x][0]] + siz[son[x][1]] + cnt[x]; } bool get(int x) { // get(x)=1 说明 x 是右儿子，反之是左儿子 return x == son[fa[x]][1]; } void clear(int x) { // 销毁结点 x son[x][0] = son[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0; } void rotate(int x) { int y = fa[x], z = fa[y]; int id = get(x); // 判断 x 是 y 的左儿子还是右儿子 if (z) son[z][get(y)] = x; fa[x] = z; son[y][id] = son[x][id ^ 1]; if (son[x][id ^ 1]) fa[son[x][id ^ 1]] = y; son[x][id ^ 1] = y, fa[y] = x; pushup(y), pushup(x); } void splay(int x, int k) { // 将 x 转到 k 的下面 while (fa[x] != k) { int y = fa[x], z = fa[y]; if (z != k) { if (get(x) ^ get(y)) rotate(x); else rotate(y); } rotate(x); } if (!k) root = x; } void insert(int k) { if (!root) { // 树为空 val[++tot] = k; ++cnt[tot]; root = tot; pushup(root); return ; } int x = root, y = 0; while (true) { if (val[x] == k) { // 找到目标 ++cnt[x]; pushup(x), pushup(y); splay(x, 0); break; } y = x, x = son[x][val[x] < k]; if (!x) { // 插入新结点 val[++tot] = k; ++cnt[tot]; fa[tot] = y; son[y][val[y] < k] = tot; pushup(tot); pushup(y); splay(tot, 0); break; } } } int get_rank(int k) { // 查询 k 的排名 int res = 0, x = root; while (true) { if (k < val[x]) x = son[x][0]; // k 落在 x 的左子树 else { res += siz[son[x][0]]; if (!x) return res + 1; if (val[x] == k) return splay(x, 0), res + 1; res += cnt[x], x = son[x][1]; } } return -1; } int get_kth(int k) { // 查询排名为 k 的数 int x = root; while (true) { if (son[x][0] && k <= siz[son[x][0]]) x = son[x][0]; else { k -= cnt[x] + siz[son[x][0]]; if (k <= 0) return splay(x, 0), val[x]; x = son[x][1]; } } return -1; } int get_pre() { // 查询根节点的前驱 int x = son[root][0]; while (son[x][1]) x = son[x][1]; splay(x, 0); return x; } int get_nxt() { // 查询根节点的后继 int x = son[root][1]; while (son[x][0]) x = son[x][0]; splay(x, 0); return x; } void erase(int k) { // 删除一个权值为 k 的数 get_rank(k); if (cnt[root] > 1) { --cnt[root]; pushup(root); return ; } if (!son[root][0] && !son[root][1]) { // 树中只有一个根结点 clear(root); root = 0; return ; } if (!son[root][0]) { // 左子树为空 int cur = root; root = son[root][1]; fa[root] = 0; clear(cur); return ; } if (!son[root][1]) { // 右子树为空 int cur = root; fa[root = son[root][0]] = 0; clear(cur); return ; } int cur = root, x = get_pre(); fa[son[cur][1]] = x; son[x][1] = son[cur][1]; clear(cur); pushup(root); } } tree; ```