非旋 Treap 模板(普通平衡树)

前言

和 Splay 一样,非旋 Treap (又名 fhq-treap)也是平衡树的一种。由于其不需要进行旋转操作,故可利用其进行可持久化。

写一颗非旋 Treap,我们只需要合并、分离操作,其他的只要有颗脑子就会了啦!

定义

我们定义类FhqTreap为非旋 Treap 主体,结构体node为其节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class FhqTheap {

private:

struct node {
int val, rnd; // val => 该点存储的值,rnd => 该点键值,随机产生
int siz, ch[2]; // siz => 该点包括其子树的节点大小,ch[2] => 指向左/右儿子
} e[maxn];
int tot, root; // tot => 节点总数,root => 根节点
int x, y, z; // 操作过程中的临时变量

// Your Code Goes Here...

public:

// Your Code Goes Here...

} s;

辅助操作

update()更新当前节点的siz

newnode()用于新建节点。

1
2
3
4
5
6
7
8
9
10
11
void update(int x) {
e[x].siz = e[e[x].ch[0]].siz + e[e[x].ch[1]].siz + 1;
}

int newnode(int val) {
tot++;
e[tot].siz = 1;
e[tot].ch[0] = e[tot].ch[1] = 0;
e[tot].val = val, e[tot].rnd = rand();
return tot;
}

合并

将树 x 与树 y 合并,默认 x < y

如果其中一颗是空树,返回另一颗;

如果树 x 的根节点的rnd小于树 y 的根节点,把 x 的右子树与 y 合并后成为 x 的右子树;

如果树 x 的根节点的rnd大于树 y 的根节点,把 y 的左子树与 x 合并后成为 y 的左子树;

等于的话随意。

1
2
3
4
5
6
7
8
9
10
11
12
int merge(int x, int y) {
if (!x || !y) return x + y;
if (e[x].rnd < e[y].rnd) {
e[x].ch[1] = merge(e[x].ch[1], y);
update(x);
return x;
} else {
e[y].ch[0] = merge(x, e[y].ch[0]);
update(y);
return y;
}
}

分离

把以某一节点为根的子树以 k 为值分为两部分。

1
2
3
4
5
6
7
8
void split(int u, int k, int &x, int &y) {
if (!u) return (void)(x = y = 0);
if (e[u].val <= k)
x = u, split(e[x].ch[1], k, e[x].ch[1], y);
else
y = u, split(e[y].ch[0], k, x, e[y].ch[0]);
update(u);
}

查找第 k 大

利用其平衡树的性质,递归写法。

1
2
3
4
5
int kth(int u, int k) {
if (k <= e[e[u].ch[0]].siz) return kth(e[u].ch[0], k);
if (k == e[e[u].ch[0]].siz + 1) return u;
return kth(e[u].ch[1], k - e[e[u].ch[0]].siz - 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
33
34
35
36
void insert(int val) {
split(root, val, x, y);
root = merge(merge(x, newnode(val)), y);
}

void erase(int val) {
split(root, val, x, z);
split(x, val - 1, x, y);
y = merge(e[y].ch[0], e[y].ch[1]);
root = merge(merge(x, y), z);
}

int rank(int val) {
split(root, val - 1, x, y);
int ret = e[x].siz + 1;
merge(x, y);
return ret;
}

int atrank(int k) {
return e[kth(root, k)].val;
}

int lower_bound(int val) {
split(root, val - 1, x, y);
int ret = e[kth(x, e[x].siz)].val;
merge(x, y);
return ret;
}

int upper_bound(int val) {
split(root, val, x, y);
int ret = e[kth(y, 1)].val;
merge(x, y);
return ret;
}

完整代码

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
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define y1 this_is_not_y1
#define y2 this_is_not_y2
#define ll long long
using namespace std;

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 100010;
int n, opt;

class FhqTheap {

private:

struct node {
int val, rnd;
int siz, ch[2];
} e[maxn];
int tot, root, x, y, z;

void update(int x) {
e[x].siz = e[e[x].ch[0]].siz + e[e[x].ch[1]].siz + 1;
}

int newnode(int val) {
tot++;
e[tot].siz = 1;
e[tot].ch[0] = e[tot].ch[1] = 0;
e[tot].val = val, e[tot].rnd = rand();
return tot;
}

int merge(int x, int y) {
if (!x || !y) return x + y;
if (e[x].rnd < e[y].rnd) {
e[x].ch[1] = merge(e[x].ch[1], y);
update(x);
return x;
} else {
e[y].ch[0] = merge(x, e[y].ch[0]);
update(y);
return y;
}
}

void split(int u, int k, int &x, int &y) {
if (!u) return (void)(x = y = 0);
if (e[u].val <= k)
x = u, split(e[x].ch[1], k, e[x].ch[1], y);
else
y = u, split(e[y].ch[0], k, x, e[y].ch[0]);
update(u);
}

int kth(int u, int k) {
if (k <= e[e[u].ch[0]].siz) return kth(e[u].ch[0], k);
if (k == e[e[u].ch[0]].siz + 1) return u;
return kth(e[u].ch[1], k - e[e[u].ch[0]].siz - 1);
}

public:

void insert(int val) {
split(root, val, x, y);
root = merge(merge(x, newnode(val)), y);
}

void erase(int val) {
split(root, val, x, z);
split(x, val - 1, x, y);
y = merge(e[y].ch[0], e[y].ch[1]);
root = merge(merge(x, y), z);
}

int rank(int val) {
split(root, val - 1, x, y);
int ret = e[x].siz + 1;
merge(x, y);
return ret;
}

int atrank(int k) {
return e[kth(root, k)].val;
}

int lower_bound(int val) {
split(root, val - 1, x, y);
int ret = e[kth(x, e[x].siz)].val;
merge(x, y);
return ret;
}

int upper_bound(int val) {
split(root, val, x, y);
int ret = e[kth(y, 1)].val;
merge(x, y);
return ret;
}

} s;

int main() {

n = read();
while (n--) {
opt = read();
switch(opt) {
case 1: s.insert(read()); break;
case 2: s.erase(read()); break;
case 3: printf("%d\n", s.rank(read())); break;
case 4: printf("%d\n", s.atrank(read())); break;
case 5: printf("%d\n", s.lower_bound(read())); break;
case 6: printf("%d\n", s.upper_bound(read())); break;
}
}

return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×