浅谈 splay

· · 算法·理论

好吧 Splay 还是太超标了。

:::warning[【显然】] 当你遇到【显然】时，请自证。 :::

0x01 平衡树

首先我们来聊聊平衡树。

顾名思义，就是平衡的树）

平衡树是一颗二叉树，左右子树高度一般相同，最多相差 1，这也保证了时间复杂度。

平衡树有很多种：

0x02 Splay

Splay，一种平衡树。

说实话，这玩意特别玄学，当然，还是有证明保证时间复杂度的。

0x03 左旋，右旋

可以看到这张图片，图丑勿喷。

先来看右旋，右旋是从左图到右图的过程。

首先，设 x 的父节点为 y，y 的父节点为 z（可以为空）。然后设出 A，B，C 三颗树，分别为 x 的左子树，x 的右子树，y 的右子树，如图所示。

让 x 代替 y，同时将 y 移动到 x 的右子树。A 还为 x 的左子树，B 变为 y 的左子树，C 还是 y 的右子树，f 部分不变。

这样就完成了 Splay 的右旋，左旋只需要反过来就可以了。

Splay 之所以这么定义左旋和右旋是因为，如果你对一颗 Splay 进行一次合法的左旋或右旋，中序遍历将不会改变。这样的性质让 Splay 成为了一种优秀的数据结构。

0x04 splay 操作

这大概是 Splay 的最重要的一个部分了。

定义函数 splay(x, k) 表示将 x 旋转到 k 的下方，特别的 k=0 表示将 x 转到根节点。

:::info[约定] 接下来将使用旋转某个节点代替左旋或右旋某个节点。

具体地：

考虑递归完成这个操作，考虑当前状态，其中 x 为要操作的节点，y 为 x 的父节点，f 为 y 的父节点。

如果 f=k 就旋转 x，退出递归就可以了。

剩下的依旧两种情况。

第一种情况中 x，y，f 成一条链直线。

第二种情况中 x，y，f 成一条折线。

这是处理这两种情况的方法。

对于第一种情况，旋转 y，旋转 x。

对于第二种情况，旋转 x，旋转 x。

图片中只给出了两种中一种的旋转方法，剩下的一个十分【显然】。

注意，虽然图片只给了一种，但是文字解释是全面的，因为旋转分 2 种，上面有定义。

作者并不知道什么叫做 zig，zig-zig，zig-zag，zag-zig 等令我晕头转向的东西，请谅解 qwq。

0x05 插入

最一般的情况，如果只给你一个数值 x 要插入的话，把 Splay 当成一颗二叉搜索树，找到 x 的位置即可。接下来，需要将 x 旋转到树根。

请注意，这一步是 Splay 时间复杂度的保证。

来看一个变种，对序列进行维护。

此时，假设我们要将序列 y 插入 x 之后。我们假设我们已经通过一种未知手段将原序列以及 y 构建成了一棵树。

设 x 的后继为 z，使用 splay(x, 0) 操作将 x 转到根，然后使用 splay(z, x) 操作将 z 转到 x 的下面，然后将 y 序列构建的树插入到 z 的左子树就可以了。

0x06 实战

终于来到了激动人心的实战时刻了！

例题：文艺平衡树

这道题目是一道不错的入门题，需要支持翻转操作。

考虑 Splay 维护什么信息。

左右儿子 ch 数组，父亲节点 p，当前节点的数值 val 必不可少。

随后，由于需要查询数组中第 pos 个数，在 Splay 树中的位置，所以需要维护一个 siz。

又因为这道题目中对区间进行操作，所以需要懒标记 laz。

懒标记下传时，只需要将左右子树调换一下，然后让 laz_{now}=0，同时让 laz_{ch_{now,0}} 和 laz_{ch_{now,1}} 反转即可。

同时，旧事重提，我们应该怎么输出最后的数列呢？

追溯到左旋，右旋部分。我们提到，Splay 的左旋，右旋可以保持 Splay 的中序遍历，所以最后直接输出 Splay 的中序遍历即可。

:::success[例题代码]

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, m, rt, idx;

struct Splay{
    int ch[2], p, v;
    int siz, laz;

    void init(int _v, int _p){
        v = _v, p = _p;
        siz = 1;
    }
} tr[N];

void pushup(int u){
    tr[u].siz = tr[tr[u].ch[0]].siz + tr[tr[u].ch[1]].siz + 1;
}

void pushdown(int u){
    if (tr[u].laz){
        swap(tr[u].ch[0], tr[u].ch[1]);
        tr[tr[u].ch[0]].laz ^= 1;
        tr[tr[u].ch[1]].laz ^= 1;
        tr[u].laz = 0;
    }
}

int getdir(int x){
    return tr[tr[x].p].ch[1] == x;
}

void output(int u){
    pushdown(u);
    if (tr[u].ch[0]) output(tr[u].ch[0]);
    if (tr[u].v >= 1 && tr[u].v <= n) cout << tr[u].v << " ";
    if (tr[u].ch[1]) output(tr[u].ch[1]);
}

void rotate(int x){
    int y = tr[x].p, z = tr[y].p;
    int a = getdir(x), b = getdir(y);
    tr[z].ch[b] = x, tr[x].p = z;
    tr[y].ch[a] = tr[x].ch[a ^ 1], tr[tr[x].ch[a ^ 1]].p = y;
    tr[x].ch[a ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x, int k){
    while (tr[x].p != k){
        int y = tr[x].p, z = tr[y].p;
        if (z != k){
            if (getdir(x) != getdir(y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if (!k) rt = x;
}

void insert(int v){
    int u = rt, p = 0;
    while (u) p = u, u = tr[u].ch[v > tr[u].v];
    u = ++ idx;
    if (p) tr[p].ch[v > tr[p].v] = u;
    tr[u].init(v, p);
    splay(u, 0);
}

int get_k(int k){
    int u = rt;
    while (1){
        pushdown(u);
        if (tr[tr[u].ch[0]].siz >= k) u = tr[u].ch[0];
        else if (tr[tr[u].ch[0]].siz + 1 == k) return u;
        else k -= tr[tr[u].ch[0]].siz + 1, u = tr[u].ch[1];
    }
    return -1; // You have no egg!
}

int main(){
    cin >> n >> m;
    for (int i = 0; i <= n + 1; i ++ ) insert(i);

    for (int i = 1; i <= m; i ++ ){
        int l, r; cin >> l >> r;
        l = get_k(l), r = get_k(r + 2);
        splay(l, 0), splay(r, l);
        tr[tr[r].ch[0]].laz ^= 1;
    }

    output(rt);
    return 0;
}

:::

:::info[代码解释] 代码中的 rotate 函数，这里实际上实现了上面为了方便叙述定义的旋转操作，是某位压行大佬发明的写法。

代码中的 insert 函数，把 Splay 当作一颗二叉搜索树。注意：这里其实不可以这么用，因为有反转操作，但是由于 insert 函数只在初始的时候使用过，所以可以这么用。

get_k 函数通过 siz 变量，找到 Splay 中按照中序遍历的第 k 个数。 :::

0x07 写在后面

很抱歉只给出了一道例题，但是希望可以起到帮助。

有问题可以在评论区提出。如果有帮助，欢迎点赞支持哦。