Splay

本文最后更新于：2022年10月13日 晚上

前言

中午写的博文，脑子不大清醒，代码直接重写的没有从写好的粘贴，如果哪里写挂了就按照代码逻辑看下去吧（反正评论区现在不大正常），实在弄不懂了可以去洛谷私信。

Intro

我们之前弄了 Treap 的平衡树，顺手我们把 Splay 的也弄了吧。

Treap 通过随机值和堆性质使得 BST 保持平衡，而 Splay 的操作则是不断将某个节点旋转到根节点，使得整棵树仍然满足 BST 的性质并且保持平衡。

我们约定几个定义：

  1. $rt$：根节点的编号
  2. $tot$：节点个数
  3. $fa_i$：表示 $i$ 的父亲
  4. $ch_{i, 0/1}$：表示左右儿子编号
  5. $val_i$：表示节点权值
  6. $cnt_i$：表示权值出现次数
  7. $siz_i$：表示子树大小

实现

Basic

upd(x)：在改变节点位置后，将节点 $x$ 的 $siz$ 更新

get(x)：判断 $x$ 是父亲节点的左儿子还是右儿子

clear(x)：移除节点 $x$

1
2
3
4
void upd(int x) {siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];}

bool get(int x) {return x == ch[fa[x]][1];}
void clear(int x) {ch[x][0] = ch[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0;}

旋转

旋转的本质其实就是将某个节点上移一个位置。

Splay 中的旋转分为左旋和右旋。

下边建议找图看，你懂的，我不想弄图这种东西。

我们假设需要旋转的节点为 $x$，它的父亲是 $y$，依旧以右旋为例。

  1. 将 $y$ 的左儿子指向 $x$ 的右儿子，且 $x$ 的右儿子（如果有的话）的父亲指向 $y$。
  2. 将 $x$ 的右儿子指向 $y$，$y$ 的父亲指向 $x$。
  3. 如果原来 $y$ 还有父亲 $z$，那么把 $z$ 原来 $y$ 所在的儿子位置指向 $x$，$x$ 的父亲指向 $z$。

其实 Splay 里边不需要写一个左旋再写一个右旋，我们一个旋转函数就好了：

1
2
3
4
5
6
7
8
9
10
11
void rorate(int x) {
    int y = fa[x], z = fa[y], chk = get(x);
    ch[y][chk] = ch[x][chk ^ 1];
    if(ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
    ch[x][chk ^ 1] = y;
    fa[y] = x;
    fa[x] = z;
    if(z) ch[z][y == ch[z][1]] = x;
    upd(y);
    upd(x);
}

Splay

这个操作规定每访问一个节点后都要强制将其转到根节点，此时旋转操作分为六种情况，用三种操作处理（可以去 OI Wiki 上看图，这里我依旧不给了）：

  1. 如果 $x$ 的父亲是根节点，直接转。
  2. 如果 $x$ 的父亲不是根节点并且 $x$ 和父亲的儿子类型相同，首先我们把父亲旋转，然后再旋转 $x$。
  3. 如果 $x$ 的父亲不是根节点并且 $x$ 和父亲的儿子类型不同，对 $x$ 左旋再右旋，或者是右旋再左旋。
1
2
3
4
5
6
void splay(int x) {
    for(int f = fa[x]; f = fa[x], f; rorate(x))
        if(fa[f]) rorate(get(x) == get(f) ? f : x);
    
    rt = x;
}

插入

我们设插入值为 $val$。

如果树空了，直接插入根并退出。

如果当前节点的权值等于 $val$ 则增加当前节点的大小并更新节点和父亲的信息，然后 splay。

否则，按照 BST 性质向下找，找到空节点插入即可，注意 splay。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void ins(int v) {
    if(!rt) {
        val[++tot] = v;
        ++cnt[tot];
        rt = tot;
        upd(rt);
        return ;
    }
    int u = rt, f = 0;
    while(true) {
        if(val[u] == v) {
            ++cnt[u];
            upd(u); // 先更新儿子再更新父亲
            upd(f);
            splay(u);
            break;
        }
        f = u;
        u = ch[u][val[u] < v];
        if(!u) { // 找到了一个空节点
            val[++tot] = v;
            ++cnt[tot];
            fa[tot] = f;
            ch[f][val[f] < v] = tot; // 看看放到哪个子树合适
            upd(tot);
            upd(f);
            splay(tot);
            break;
        }
    }
}

查询 $x$ 的排名

如果 $x$ 比当前节点权值小，去左子树找。

如果比当前节点权值大，那么我们把答案加上左子树和当前节点的大小，向右子树找。

如果相等，将答案加上 1 返回。

最后还要 splay。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int get_rk(int v) {
    int res = 0, u = rt;
    while(true) {
        if(v < val[u]) u = ch[u][0];
        else {
            res += siz[c[u][0]];
            if(v == val[u]) {
                splay(u);
                return res + 1;
            }
            res += cnt[u];
            u = ch[u][1];
        }
    }
}

查询排名为 $k$ 的数

设 $k$ 为剩余排名。

如果左子树非空并且 $k$ 不大于左子树大小，向左子树中查找。

否则，将 $k$ 减去左子树和根的大小，如果 $k$ 小于等于 0 说明这个点在根上，返回根节点的权值即可，否则继续向右子树查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int get_val(int k) {
    int u = rt;
    while(true) {
        if(ch[u][0] && k <= siz[ch[u][0]]) u = ch[u][0];
        else {
            k -= (cnt[u] + siz[ch[u][0]]);
            if(k <= 0) {
                splay(u);
                return val[u];
            }
            u = ch[u][1];
        }
    }
}

查找前驱

查询 $v$ 的前驱可以转化为：将 $v$ 插入（因为 splay 操作，$v$ 已经在根的位置了），前驱为根的左子树中最大的节点，最后删除 $v$ 即可。

1
2
3
4
5
6
7
int get_pre() {
    int u = ch[rt][0];
    if(!u) return u;
    while(ch[u][1]) u = ch[u][1];
    splay(u);
    return u;
}

合并与删除

合并两颗 Splay 树，设两树根节点分别为 $x$ 和 $y$，我们要求 $x$ 树中的最大值小于 $y$ 树中的最小值。

如果 $x$ 和 $y$ 其中之一或者是两者都为空树，直接返回不为空的那一棵树的根节点或者是空树。

否则将 $x$ 树中的最大值 Splay 到根，然后把它的右子树设置为 $y$ 并更新节点的信息，然后返回这个节点。

删除 $x$，首先将 $x$ 转到根的位置，如果 $cnt_x > 1$ ，直接将 $cnt_x$ 减 1 并退出。

否则，合并它的左右两棵子树即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void del(int v) {
    rk(v);
    if(cnt[rt] > 1) {
        --cnt[rt];
        upd(rt);
        return ;
    }
    if(!ch[rt][0] && !ch[rt][1]) {
        clear(rt);
        rt = 0;
        return ;
    }
    if(!ch[rt][0]) {
        int u = rt;
        rt = ch[rt][1];
        fa[rt] = 0;
        clear(u);
        return ;
    }
    if(!ch[rt][1]) {
        int u = rt;
        rt = ch[rt][0];
        fa[rt] = 0;
        clear(u);
        return ;
    }
    int u = rt, x = pre();
    fa[ch[u][1]] = x;
    ch[x][1] = ch[u][1];
    clear(u);
    upd(rt);
}

根据我们写数据结构要封装的良好习惯，我们可以这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
struct Splay {
    int siz[N];
    int tot, fa[N], ch[N][2], val[N], cnt[N];
    int rt;

    void upd(int x) { siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];}
    bool get(int x) { return x == ch[fa[x]][1];}
    void clear(int x) { ch[x][0] = ch[x][1] = fa[x] = val[x] = siz[x] = cnt[x] = 0;}

    void rorate(int x) {
        int y = fa[x], z = fa[y], chk = get(x);
        ch[y][chk] = ch[y][chk ^ 1];

        if(ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;
        ch[x][chk ^ 1] = y;
        fa[y] = x;
        fa[x] = z;
        if(z) ch[z][y == ch[z][1]] = x;
        upd(y), upd(x);
    }

    void splay(int x) {
        for(int f = fa[x]; f = fa[x], f; rorate(x))
            if(fa[f]) rorate(get(x) == get(f) ? f : x);

        rt = x;
    }

    void add(int v) {
        if(!rt) {
            val[++tot] = v;
            ++cnt[tot];
            rt = tot;
            upd(rt);
            return ;
        }

        int u = rt, f = 0;
        while(true) {
            if(val[u] == v) {
                ++cnt[u];
                upd(u);
                upd(f);
                splay(u);
                break;
            }
            f = u;
            u = ch[u][val[u] < v];
            if(!u) {
                val[++tot] = v;
                ++cnt[tot];
                fa[tot] = f;
                ch[f][val[f] < v] = tot;
                upd(tot);
                upd(f);
                splay(tot);
                break;
            }
        }
    }

    int get_rk(int v) {
        int res = 0, u = rt;
        while(true) {
            if(v < val[u]) u = ch[u][0];
            else {
                res += siz[ch[u][0]];
                if(v == val[u]) {
                    splay(u);
                    return res + 1;
                }
                res += cnt[u];
                u = ch[u][1];
            }
        }
    }

    int get_v(int rk) {
        int u = rt;
        while(true) {
            if(ch[u][0] && rk <= siz[ch[u][0]]) u = ch[u][0];
            else {
                rk -= cnt[u] + siz[ch[u][0]];
                if(rk <= 0) {
                    splay(rk);
                    return val[u];
                }
                u = ch[u][1];
            }
        }
    }

    int get_pre() {
        int u = ch[rt][0];
        if(!u) return u;
        while(ch[u][1]) u = ch[u][1];
        splay(u);
        return u;
    }

    int get_nxt() {
        int u = ch[rt][1];
        if(!u) return u;
        while(ch[u][0]) u = ch[u][0];
        splay(u);
        return u;
    }

    void del(int v) {
        get_rk(v);
        if(cnt[rt] > 1) {
            --cnt[rt];
            upd(rt);
            return ;
        }
        if(!ch[rt][0] && !ch[rt][1]) {
            clear(rt);
            rt = 0;
            return ;
        }
        if(!ch[rt][0] && !ch[rt][1]) {
            clear(rt);
            rt = 0;
            return ;
        }
        if(!ch[rt][0]) {
            int u = rt;
            rt = ch[rt][1];
            fa[rt] = 0;
            clear(u);
            return ;
        }
        if(!ch[rt][1]) {
            int u = rt;
            rt = ch[rt][0];
            fa[rt] = 0;
            clear(u);
            return ;
        }
        int u = rt;
        int x = get_pre();
        fa[ch[u][1]] = x;
        ch[x][1] = ch[u][1];
        clear(u);
        upd(rt);
    }
}spl;
OI
#Data Structure
Splay
http://dxrprime.github.io/2022/08/25/Splay/
作者
Shelter Prime
发布于
2022年8月25日
许可协议