因为考试考了LCT发现不会写所以干脆从平衡树开始复盘数据结构祭
参考资料 ：
自为风月马前卒的博客
oi-wiki(mirror)
LordLaffey’s Code

目标

实现一种数据结构，维护以下功能 ：

  • 插入数 $x$
  • 删除一个数 $x$
  • 查询数 $x$ 的排名
  • 查询排名为 $x$ 的数
  • 求 $x$ 的前驱
  • 求 $x$ 的后继

其实就是模板题P3369

使用pb_ds实现

gnu送的平衡树，可以这样用 ： 

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
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
namespace Pozhu{
using namespace std;
using namespace __gnu_pbds;
#define Pair pair<int ,int >
struct pb_tree
{
    int tot = 0;
    tree < Pair ,null_type ,less<Pair> ,rb_tree_tag,
    tree_order_statistics_node_update > tr;
    void insert(int val)
    {
        tr.insert(make_pair(val,++tot));
    }
    void erase(int val)
    {
        auto it = tr.lower_bound(make_pair(val,0));
        if(it -> first == val) tr.erase(it);
    }
    int get_rank(int val)
    {
        return tr.order_of_key(make_pair(val,0)) + 1;
    }
    int get_kth(int k)
    {
        if(k > tr.size()) return INT_MAX;
        return tr.find_by_order(k - 1) -> first;
    }
    int get_pre(int val)
    {
        auto it = tr.lower_bound(make_pair(val,0));
        if(it == tr.begin()) return -INT_MAX;
        else return (--it) -> first;
    }
    int get_next(int val)
    {
        auto it = tr.lower_bound(make_pair(val + 1,0));
        if(it == tr.end()) return INT_MAX;
        else return it -> first;
    }
}t;
int n;

void main()
{
    scanf("%d",&n);
    int x,opt;
    for(int i = 1;i<=n;i++)
    {
        scanf("%d%d",&opt,&x);
        if(opt == 1) t.insert(x);
        else if(opt == 2) t.erase(x);
        else if(opt == 3) printf("%d\n",t.get_rank(x));
        else if(opt == 4) printf("%d\n",t.get_kth(x));
        else if(opt == 5) printf("%d\n",t.get_pre(x));
        else if(opt == 6) printf("%d\n",t.get_next(x));
    }
    return;
}

}

int main()
{
    Pozhu :: main();
    return 0;
}

优点是好写不易锅也不易被卡。

使用 无旋Treap 实现

无旋Treap 是一种操作基于分裂 split 和合并 merge 的数据结构，不需要通过旋转来维护平衡

基本操作

maintain

使用子节点跟更新父节点的信息

1
void maintain(int x){siz[x] = cnt[x] + siz[son[x][0]] + siz[son[x][1]];}

clear

删除无用的节点

1
void clear(int x){son[x][0] = son[x][1] = siz[x] = val[x] = cnt[x] = key[x] = 0;}

newnode

新建节点

1
void clear(int x){son[x][0] = son[x][1] = siz[x] = val[x] = cnt[x] = key[x] = 0;}

分裂 split

有两种常见的分裂方式 ： 按值分裂和按大小（排名）分裂。

按值分裂

先贴代码，含义是将以 p 为根的子树以小于等于 v 为界限分裂到以 x 和 y 为根的两个子树中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void split(int p,int v,int &x,int &y)
{
    if(!p) return x = y = 0,void();
    if(val[p] <= v)
    {
        x = p;
        split(son[p][1],v,son[x][1],y);
    }
    else
    {
        y = p;
        split(son[p][0],v,x,son[y][0]);
    }
    maintain(p);
}

由于二叉搜索树的性质，可以得到if语句的含义

当 val[p] <= v 时，显然整棵左子树都不会被分割。于是把 x 设为当前节点的左子树，递归去分裂右子树并将其分裂出来的左半部分并入 x 中。

当 val[p] > v 时，显然整棵右子树都不会被分割。于是把 y 设为当前节点的右子树，递归去分裂左子树并将其分裂出来的右半部分并入 y 中。

按大小分裂

先贴代码，含义是将以 p 为根的子树以第 v 个元素为界限分裂到以 x 和 y 为根的两个子树中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void split(int p,int v,int &x,int &y)
{
    if(!p) return x = y = 0,void();
    push_down(p);
    if(siz[ls(p)] + cnt[p] <= v)
    {
        x = p;
        split(rs(p),v-siz[ls(p)]-cnt[p],rs(x),y);
    }
    else
    {
        y = p;
        split(ls(p),v,x,ls(y));
    }
    maintain(p);
}

与按值分裂不同的地方大概就在于分裂右子树时要注意减去左子树和当前节点的大小

其他的都差不多。

合并 merge

依旧是先贴代码，含义是合并以 x , y 为根的两棵树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int merge(int x,int y)
{
    if(!x || !y) return x|y;
    if(key[x] > key[y])
    {
        son[x][1] = merge(son[x][1],y);
        maintain(x);
        return x;
    }
    else
    {
        son[y][0] = merge(x,son[y][0]);
        maintain(y);
        return y;
    }
}

代码中 key 是每个结点的随机值。这里的合并采用了大根堆（其实小根堆也可以，也就是第二个 if 中的大于号可以换成小于号）

第一个 if 语句是合并过程复杂度的保证。

然后应该不用解释啥了（

剩下的操作

剩下的操作都很好做：

  • 插入： 按照值 $x$ 分裂树，合并左半边，新节点($x$)，右半边。
  • 删除： 按值 $x$ 分裂树，左半边再按照 $x-1$ 分裂为 $a$,$b$ ，于是我们得到的树 $b$ 中全都是值为$x$ 的节点，合并根节点的左右子树就可以删去一个值为 $x$ 的节点。
  • 查排名： 按值 $x$ 分裂树，排名即为左半棵树大小 $+1$ 。
  • 查前驱： 按值 $x-1$ 分裂树，左半棵树一直向右走的最右边的一个节点即为前驱。
  • 查后继： 按值 $x$ 分裂树，右半棵树的最左边一个节点即为后继。

然后放一下模板题的代码 ： 

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
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 500010
int n,m;
int a[N];
int root,tot;
mt19937 rnd(time(0));
int son[N][2];
int val[N],siz[N];
int key[N],cnt[N];

void maintain(int x){siz[x] = cnt[x] + siz[son[x][0]] + siz[son[x][1]];}
void clear(int x){son[x][0] = son[x][1] = siz[x] = val[x] = cnt[x] = key[x] = 0;}
int newnode(int v){tot++;key[tot] = rnd(),siz[tot] = cnt[tot] = 1;val[tot] = v;return tot;}
void split(int p,int v,int &x,int &y)
{
    if(!p) return x = y = 0,void();
    if(val[p] <= v)
    {
        x = p;
        split(son[p][1],v,son[x][1],y);
    }
    else
    {
        y = p;
        split(son[p][0],v,x,son[y][0]);
    }
    maintain(p);
}
int merge(int x,int y)
{
    if(!x || !y) return x|y;
    if(key[x] > key[y])
    {
        son[x][1] = merge(son[x][1],y);
        maintain(x);
        return x;
    }
    else
    {
        son[y][0] = merge(x,son[y][0]);
        maintain(y);
        return y;
    }
}
void insert(int k)
{
    int x,y;
    split(root,k,x,y);
    root = merge(merge(x,newnode(k)),y);
}
void del(int k)
{
    int x,y,z;
    split(root,k,x,z);
    split(x,k-1,x,y);
    y = merge(son[y][0],son[y][1]);
    root = merge(merge(x,y),z);
}
int rnk(int k)
{
    int x,y;
    split(root,k-1,x,y);
    k = siz[x]+1;
    root = merge(x,y);
    return k;
}
int kth(int rnk)
{
    if(!root) return -1;
    int cur = root;
    while(cur)
    {
        if(son[cur][0] && rnk <= siz[son[cur][0]])
            cur = son[cur][0];
        else
        {
            rnk -= cnt[cur] + siz[son[cur][0]];
            if(rnk <= 0) return val[cur];
            cur = son[cur][1];
        }
    }
    return -1;
}
int pre(int k)
{
    int x,y;
    split(root,k-1,x,y);
    int cur = x;
    if(!cur) return cur;
    while(son[cur][1]) cur = son[cur][1];
    root = merge(x,y);
    return cur;
}
int nxt(int k)
{
    int x,y;
    split(root,k,x,y);
    int cur = y;
    if(!cur) return cur;
    while(son[cur][0]) cur = son[cur][0];
    root = merge(x,y);
    return cur;
}
void main()
{
    scanf("%d",&n);
    while(n--)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt == 1) insert(x);
        else if(opt == 2) del(x);
        else if(opt == 3) printf("%d\n",rnk(x));
        else if(opt == 4) printf("%d\n",kth(x));
        else if(opt == 5) printf("%d\n",val[pre(x)]);
        else if(opt == 6) printf("%d\n",val[nxt(x)]);
    }
    return;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

使用 Splay 实现

（现学现卖）

splay 是平衡树的一种，主要思想是: 对于查找频率较高的节点，使其处于离根节点相对较近的节点

为了保证平衡，我们会在每次查找一个点之后把这个点旋转到根节点去。

基本操作

maintain 用子节点的信息更新父节点

1
void maintain(int x) {siz[x] = siz[ls(x)] + siz[rs(x)] + cnt[x];}

get 返回当前节点是父节点的左儿子还是右儿子

1
bool get(int x){return x == rs(fa[x]);}

clear清空当前节点

1
void clear(int x) {ls(x) = rs(x) = fa[x] = val[x] = siz[x] = cnt[x] = 0;}

rotate旋转

使用这个函数可以实现splay的旋转操作，具体来讲，就是把某个节点与它父亲调换位置。

旋转需要保证 ：

  • 整棵splay的中序遍历不变（BST性质不被破坏）
  • 旋转中涉及到的节点维护的信息依然正确
  • root必须指向正确的根节点

这个操作dalao自为风月马前卒讲解的非常详细，这里就抄一遍（

假设我们要旋转的节点是点 $X$ ，它的父亲是点 $Y$ ，他的爷爷是点 $R$ 。

那么我们要分两大类情况 ：

一、 $X$ 是 $Y$ 的左儿子

像这样（盗的图）：

盗的图

根据BST的性质，B会成为Y的左儿子，Y会成为X的右儿子，X会成为R的和Y相同的儿子（代替Y在R心目中的地位）

经过变换之后大概是这样 ：

盗的图

经过形象理解，我认为可以这样解释这个旋转 ：

把它从“旋转”的形象中脱离开，看成“提拔”。

我们把X和它远离Y的左子树提起来，另外一棵子树不管（就会自动连到Y上）。然后X向上移插入到R和Y的中间，就形成了“提拔”之后的样子。

二、$X$ 是 $Y$ 的右儿子

像这样 ：

盗的图

同理可以想象到，旋转后是这样 ：

盗的图

看成“提拔”也很直观。

考虑将这两种旋转写到同一份代码中，这要求我们弄清楚两份旋转与他们父子左右关系的性质（前边我们已经实现了get函数）。

显然B代替了X在Y心目中的位置，那么B的儿子属性是与X相同的。

显然X代替了Y在R心目中的位置，那么X的儿子属性是与Y相同的。

因为X与Y在图中的绝对左右关系不变，而父子关系颠倒，所以Y的儿子属性与X的儿子属性相反。

然后稍微理一下我们更新时的先后顺序……

欸嘿，于是我们可以写出rotate函数 ： 

1
2
3
4
5
6
7
8
9
10
11
12
void rotate(int X)
{
    int Y = fa[X],R = fa[Y];
    int flag = get(X);
    son[Y][flag] = son[X][flag^1];
    if(son[X][flag^1]) fa[son[X][flag^1]] = Y;
    son[X][flag^1] = Y;
    fa[Y] = X,fa[X] = R;
    if(R) son[R][Y == rs(R)] = X;
    maintain(X);
    maintain(Y);
}

Splay 换根

我们使用splay(x) 来实现把 $x$ 旋转到根的操作。

显然每次直接旋转 $x$ 不能使树高减小，这不利于我们维护平衡树性质。

进行一个叫做“双旋”的操作则可以使路径上所有点的深度变为原来的大约一半，其他节点的深度最多加 $2$ （不会证）。

经过《简单分析》我们可以得出 ：

  • 如果 $X$ 到他爷爷都在一条直线上，我们就先转他爸爸再转他

  • 如果 $X$ 到他爷爷形成了一个“之”字形（容易得出只有这两种情况），我们就旋转两次 $X$

然后综合一下以上两个情况，我们就可以得到一个美观简洁的写法 ： 

1
2
3
4
5
6
7
8
//sto LordLaffey orz
void splay(int x)
{
    for(int f = fa[x];f = fa[x],f;rotate(x))
    if(fa[f])
        rotate(get(x) == get(f) ? f : x);
    root = x;
}

（所以对着大佬的板子抄一遍作为一个数据结构的入门是很好的，这可以让你学到很多美观简洁的写法……不过一定要一句一句地理清楚然后试着自己敲，不然背不过板子）

于是我们理完了splay的核心操作。

剩下的操作

（但是splay剩下的操作不能像非旋Treap那样一笔带过），于是考虑在代码里写注释方便理解

insert 插入

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
void insert(int k)
{
    if(!root)
    {//特判树为空的情况
        val[++tot] = k;
        cnt[tot]++;
        root = tot;
        maintain(root);
        return;
    }
    
    int cur = root ,f = 0;
    while(1)
    {
        if(val[cur] == k)
        {//有且找到了要加入的权值
            cnt[cur] ++;//那么这个权值的副本数+1
            maintain(cur);
            maintain(f);
            splay(cur);//当前节点旋转到根
            return;
        }
        f = cur;//观察上下文可得f是更新后的cur的父亲
        cur = son[cur][val[cur] < k];//当前节点的权值小于k，则要走右子树找更大权值，反之亦然
        if(!cur)
        {//当前没有要插入的这个权值的节点，新建一个
            val[++tot] = k;
            cnt[tot] ++;
            fa[tot] = f;
            son[f][val[f] < k] = tot;//更新父亲的儿子信息
            maintain(tot);
            maintain(f);
            splay(tot);
            return;
        }
    }
}

rnk 查询排名

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int rnk(int k)
{
    int res = 0,cur = root;//res是当前已经得到的信息中比k小的数有几个
    while(1)
    {
        if(k < val[cur])//此时我们要进入左子树，不能知道有几个比k小的数
            cur = ls(cur);
        else
        {
            res += siz[ls(cur)];//左子树都比k小，res加上左子树的大小
            if(k == val[cur])
            {
                splay(cur);
                return res + 1;//排名就是比他小的数的数量+1
            }
            res += cnt[cur];//当前节点及所有副本都比k小
            cur = rs(cur);
        }
    }
}

kth 查询排名对应的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int kth(int rnk)
{//这是一个类似于线段树二分的过程
    int cur = root;
    while(1)
    {
        if(ls(cur) && rnk <= siz[ls(cur)])//如果存在左儿子且左儿子的大小小于要查的排名
            cur = ls(cur);//进入左子树
        else
        {
            rnk -= cnt[cur] + siz[ls(cur)];//在右子树中查询剩下的排名
            if(rnk <= 0)
            {//要查的是当前节点而不是右子树
                splay(cur);
                return val[cur];
            }
            cur = rs(cur);//进入右子树
        }
    }
}

pre 查询前驱

1
2
3
4
5
6
7
8
9
10
11
if(opt == 5) insert(x),printf("%d\n",val[pre()]),del(x);
//为了保证有这个节点，先插入一个节点再删除。insert时已经把他转到根了，所以只需要查询根节点的前驱即可
//根据BST的性质，根节点的前驱就是进入左子树然后一直向右走
int pre()
{
    int cur = ls(root);
    if(!cur) return cur;
    while(rs(cur)) cur = rs(cur);
    splay(cur);
    return cur;
}

nxt 查询后继

和前驱很像，只是进入右子树后一直向左走

1
2
3
4
5
6
7
8
9
if(opt == 6) insert(x),printf("%d\n",val[nxt()]),del(x);
int nxt()
{
    int cur = rs(root);
    if(!cur) return cur;
    while(ls(cur)) cur = ls(cur);
    splay(cur);
    return cur;
}

del 删除节点

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
void del(int k)
{
    rnk(k);//先把这个点转到根
    if(cnt[root] > 1)
    {//如果它有不止一个副本，那么删除一个副本之后就可以直接退出
        cnt[root] --;
        maintain(root);
        return;
    }
    //否则它只有一个副本，合并它的子树即可
    if(!ls(root) || !rs(root))
    {//它的子树不全
        int cur = root;
        root = ls(root) | rs(root);//显然都是0是就删成了空树，否则存在的儿子是根
        fa[root] = 0;
        clear(cur);
        return;
    }
    //那么它拥有两棵子树
    int cur = root,x = pre();//注意此时的root已经变成了原root的前驱，cnt内存的是原root
    fa[rs(cur)] = x;//原来的右子树根据BST性质成为原前驱的右儿子
    rs(x) = rs(cur);
    clear(cur); //清除掉旧的根
    maintain(root);
}

然后再放一个整道题的代码 ： 

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include<bits/stdc++.h>
namespace Pozhu{
using namespace std;
#define N 500010

int n;
int val[N];
int root,tot;
int siz[N],cnt[N];
int fa[N],son[N][2];

#define ls(x) (son[x][0])
#define rs(x) (son[x][1])

void maintain(int x) {siz[x] = siz[ls(x)] + siz[rs(x)] + cnt[x];}
bool get(int x){return x == rs(fa[x]);}
void clear(int x) {ls(x) = rs(x) = fa[x] = val[x] = siz[x] = cnt[x] = 0;}

void rotate(int x)
{
    int y = fa[x],z = fa[y];
    int flag = get(x);
    son[y][flag] = son[x][flag^1];
    if(son[x][flag^1]) fa[son[x][flag^1]] = y;
    son[x][flag^1] = y;
    fa[y] = x,fa[x] = z;
    if(z) son[z][y == rs(z)] = x;
    maintain(x);
    maintain(y);
}

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

void insert(int k)
{
    if(!root)
    {
        val[++tot] = k;
        cnt[tot]++;
        root = tot;
        maintain(root);
        return;
    }
    
    int cur = root ,f = 0;
    while(1)
    {
        if(val[cur] == k)
        {
            cnt[cur] ++;
            maintain(cur);
            maintain(f);
            splay(cur);
            return;
        }
        f = cur;
        cur = son[cur][val[cur] < k];
        if(!cur)
        {
            val[++tot] = k;
            cnt[tot] ++;
            fa[tot] = f;
            son[f][val[f] < k] = tot;
            maintain(tot);
            maintain(f);
            splay(tot);
            return;
        }
    }
}

int rnk(int k)
{
    int res = 0,cur = root;
    while(1)
    {
        if(k < val[cur])
            cur = ls(cur);
        else
        {
            res += siz[ls(cur)];
            if(k == val[cur])
            {
                splay(cur);
                return res + 1;
            }
            res += cnt[cur];
            cur = rs(cur);
        }
    }
}

int kth(int rnk)
{
    int cur = root;
    while(1)
    {
        if(ls(cur) && rnk <= siz[ls(cur)])
            cur = ls(cur);
        else
        {
            rnk -= cnt[cur] + siz[ls(cur)];
            if(rnk <= 0)
            {
                splay(cur);
                return val[cur];
            }
            cur = rs(cur);
        }
    }
}

int pre()
{
    int cur = ls(root);
    if(!cur) return cur;
    while(rs(cur)) cur = rs(cur);
    splay(cur);
    return cur;
}

int nxt()
{
    int cur = rs(root);
    if(!cur) return cur;
    while(ls(cur)) cur = ls(cur);
    splay(cur);
    return cur;
}

void del(int k)
{
    rnk(k);
    if(cnt[root] > 1)
    {
        cnt[root] --;
        maintain(root);
        return;
    }
    
    if(!ls(root) || !rs(root))
    {
        int cur = root;
        root = ls(root) | rs(root);
        fa[root] = 0;
        clear(cur);
        return;
    }
    
    int cur = root,x = pre();
    fa[rs(cur)] = x;
    rs(x) = rs(cur);
    clear(cur);
    maintain(root);
}

void main()
{
    scanf("%d",&n);
    while(n--)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt == 1) insert(x);
        else if(opt == 2) del(x);
        else if(opt == 3) printf("%d\n",rnk(x));
        else if(opt == 4) printf("%d\n",kth(x));
        else if(opt == 5) insert(x),printf("%d\n",val[pre()]),del(x);
        else if(opt == 6) insert(x),printf("%d\n",val[nxt()]),del(x);
    }
    return;
}

}

signed main()
{
    Pozhu :: main();
    return 0;
}

用替罪羊树实现

先咕力。

Pozhu
2022.8.25

——以及全站字数破5w祭