抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

浅析FHQ-treap

数据结构平衡树

发布于：2024年11月28日

fhq-treap 又名“无旋 treap”，有着码量小，易理解，可持久化等特点。

luogu 阅读链接。

前言

fhq-treap 又名“无旋 treap”，有着码量小，易理解，可持久化等特点。
但 fhq-treap 的常数较大。
必要：

选要：

基础操作

treap 的每个节点都有一个随机的优先级。
treap 的权值要具有二叉搜索树的性质，优先级满足堆的性质。
fhq-treap 有两个关键函数 slipt 和 merge，分别是分裂和合并。
代码中均为小根堆。

节点

在 fhq-treap 中我们需要维护子树大小，节点权值，左右儿子，优先级（随机数，用于堆）。

1
2
3
4
5
6
7
8
9
10
11
12
std::mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());
//需要 <random> 和 <chrono> 头文件，不要放在结构体内
struct node{
    int size, val, rank, ls, rs;
}d[N];
int tot = 0, root = 0;
int newnode(int val){
    d[++tot].val = val, d[tot].rank = rd();
    d[tot].size = 1, d[tot].ls = d[tot].rs = 0;
    return tot;
}
void getsize(int u){d[u].size = 1 + d[d[u].ls].size + d[d[u].rs].size;}

分裂

按权值分裂

图
明显，我们会把一个树，把权值 ≤k\le k 的放在 L 树中，>k> k 的放在 R 树中。

1
2
3
4
5
6
void SplitVal(int now, int val, int&L, int&R){
    if(!now)return void(L = R = 0);
    if(d[now].val <= val)L = now, SplitVal(d[now].rs, val, d[now].rs, R);
    else R = now, SplitVal(d[now].ls, val, L, d[now].ls);
    return getsize(now);
}

我们理解一下代码。
我们现在遍历到了原树的 now 节点。
如果节点是空的那么 L 和 R 树都是空的。

如果这个节点的权值 ≤k\le k：
    ~~~~ 那么我们把他放在 L 树中，然后行对 now 节点的右儿子遍历，由于是二叉搜索树，所以 now 的左儿子的权值均 ≤k\le k，所以只用考虑分割 now 的右儿子的是在 L 树的右儿子，还是在 R 树内。

反之同理。

按排名分裂

同理，只不过要判断左儿子的大小关系。

1
2
3
4
5
6
7
void SplitRank(int now, int k, int&L, int&R){
    if(!now)return void(L = R = 0);
    int size = d[d[now].ls].size;
    if(k <= size)R = now, SplitRank(d[now].ls, k, L, d[R].ls);
    else L = now, SplitRank(d[L].rs, k - size - 1, d[L].rs, R);
    getsize(now);
}

合并

合并是分裂的逆操作，我们回到之前的这幅图。
图
如果要合并，我们需要保证 ∀x∈L,y∈R,val(x)≤val(y)\forall x \in L, y \in R, val(x) \le val(y)。
由于两棵树有序，只需要根据优先级考虑哪颗树放“上面”，哪棵树放“下面”，即考虑哪棵树成为子树。
同时，我们还需要满足二叉搜索树的性质。
所以若 LL 的根结点的优先级 <R< R 的，则 LL 成为根结点，由于 RR 的权值 ≥L\ge L，所以 RR 和 LL 的右子树合并；
反之，则 RR 作为根结点，LL 和 RR 的左子树合并。

1
2
3
4
5
6
7
8
9
10
11
int merge(int L, int R){
    if(!L || !R)return L + R;
    if(d[L].rank < d[R].rank){
        d[L].rs = merge(d[L].rs, R), getsize(L);
        return L;
    }
    else {
        d[R].ls = merge(L, d[R].ls), getsize(R);
        return R;
    }
}

其他

有了分裂和合并，剩下的函数就很好实现了。

插入

新建的节点的权值的 valval，我们将 ≤val\le val 和 >val> val 的分裂，然后将新建的节点合并。

1
2
3
4
5
void insert(int val){
    int L, R;
    SplitVal(root, val, L, R);
    root = merge(merge(L, newnode(val)), R);
}

这样我们需要调用一次分裂和两次合并，常数明显很大。
我们可以优化：

1
2
3
4
5
6
void insert(int val){
    int*u = &root, z = newnode(val), r = d[z].rank;
    for(;*u && (d[*u].rank < r);u = &(val < d[*u].val ? d[*u].ls : d[*u].rs))
        ++d[*u].size;
    SplitVal(*u, val, d[z].ls, d[z].rs), *u = z, getsize(z);
}

我们可以用循环寻找我们要插入的位置，然后把路径上的点的子树大小增加。
接着将这个位置原本的树按权值分裂成两棵，然后放在插入节点的两个儿子。

删除

我们将 <val< val、=val= val 和 >val> val，的部分分裂出来，最中间的那棵树就是要删除的。
由于只要删除一个数，我们将中间部分的左右儿子合并，然后将剩余的部分合并。

1
2
3
4
5
6
7
void del(int val){
    int L, mid, R;
    SplitVal(root, val, L, R);
    SplitVal(L, val - 1, L, mid);
    mid = merge(d[mid].ls, d[mid].rs);
    root = merge(merge(L, mid), R);
}

我们用相似的方式进行优化。
因为题目保证删除的点存在（不保证就找到后再扫一遍），我们直接将路径上的子树大小修改。
然后将删除点的两个子树拼起来，放在删除点的原本位置。

1
2
3
4
5
void del(int val){
    int*u =&root;
    for(;*u && d[*u].val != val;u = &(val < d[*u].val ? d[*u].ls : d[*u].rs))--d[*u].size;
    if(u) *u = merge(d[*u].ls, d[*u].rs);
}

查询部分

可以像开头 BST 的那样询问，也可以像这里借助分裂合并（常数较大）：

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
//我们将 < x 的分裂出，然后一直往右走，走到头就是前驱。
int pre_val(int x){
    int L, R, now;
    SplitVal(root, x - 1, L, R), now = L;
    while(d[now].rs)now = d[now].rs;
    return root = merge(L, R), d[now].val;
}
//类似
int next_val(int x){
    int L, R, now;
    SplitVal(root, x, L, R), now = R; 
    while(d[now].ls)now = d[now].ls;
    return root = merge(L, R), d[now].val;
}
//将 < x 的分裂，答案就是这棵树的大小。
int query_rank(int val){
    int L, R;
    SplitVal(root, val - 1, L, R);
    int ans = d[L].size + 1;
    return root = merge(L, R), ans;
} 
//和 BST 中一样
int kth(int k, int rak){
    while(1){
        if (rak <= d[d[k].ls].size)k = d[k].ls;
        else if (!(rak -= d[d[k].ls].size + 1))return d[k].val;
        else k = d[k].rs;
    }
}

完整代码

P3369 普通平衡树。
P3369 插入删除优化
P6136 普通平衡树加强版。

序列操作

我们可以将树的中序遍历看做序列顺序的。
然后用按排名分裂，分成 [1,l−1],[l,r],[r+1,n][1, l - 1], [l, r], [r + 1, n] 三块。
给中间的块打上标记，之后在访问的时候 pushdown 即可。

例题：

P3391 文艺平衡树代码。
P2042 维护序列。

可持久化

不知道什么是可持久化的看这：可持久化数据结构简介。
打上注释的是添加的操作。

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 split(int now, int val, int&L, int&R){
    if(!now)return void(L = R = 0);
    int w;
    if(d[now].val <= val){
        d[L = newnode(1)] = d[now];//
        split(d[now].rs, val, d[L].rs, R), getsize(L);
    }
    else {
        d[R = newnode(1)] = d[now];//
        split(d[now].ls, val, L, d[R].ls), getsize(R);
    }
    return getsize(L);
}
int merge(int L, int R){
    if(!L || !R)return L + R;
    int w;
    if(d[L].rank < d[R].rank){
        d[w = newnode(1)] = d[L];//
        return d[w].rs = merge(d[w].rs, R), getsize(w), w;
    }
    else {
        d[w = newnode(1)] = d[R];//
        return d[w].ls = merge(L, d[w].ls), getsize(w), w;
    }
}

记得用一个数组存一下每个版本的根。

例题

P3835 可持久化平衡树

模版，直接往上套。

代码

由于借鉴了题解，我又懒得重写，所以这里的码风不好
洛谷云剪贴板

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
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 5e7 + 10;
int rt[N];
std::mt19937 rd(std::chrono::steady_clock::now().time_since_epoch().count());
struct treap{
	struct node{int size, val, rank, ls, rs;}d[N];
	int tot = 0, root = 0;
	int newnode(int val){d[++tot].val = val, d[tot].rank = rd(), d[tot].size = 1, d[tot].ls = d[tot].rs = 0;return tot;}
	void getsize(int u){if(u)d[u].size = 1 + d[d[u].ls].size + d[d[u].rs].size;}
	void split(int now, int val, int&L, int&R){
		if(!now)return void(L = R = 0);
		int w;
		if(d[now].val <= val){
			d[L = newnode(1)] = d[now];//
			split(d[now].rs, val, d[L].rs, R), getsize(L);
		}
		else {
			d[R = newnode(1)] = d[now];//
			split(d[now].ls, val, L, d[R].ls), getsize(R);
		}
		return getsize(L);
	}
	int merge(int L, int R){
		if(!L || !R)return L + R;
		int w;
		if(d[L].rank < d[R].rank){
			d[w = newnode(1)] = d[L];//
			return d[w].rs = merge(d[w].rs, R), getsize(w), w;
		}
		else {
			d[w = newnode(1)] = d[R];//
			return d[w].ls = merge(L, d[w].ls), getsize(w), w;
		}
	}
	void insert(int val){int L, R;split(root, val, L, R), root = merge(merge(L, newnode(val)), R);}
	void del(int val){
		int L, mid, R;
		split(root, val, L, R), split(L, val - 1, L, mid);
		mid = merge(d[mid].ls, d[mid].rs), root = merge(merge(L, mid), R);
	}
	int kth(int rt, int k) {
		d[0].size = 0;
		while(1) {        
			if(k <= d[d[rt].ls].size) rt = d[rt].ls;
			else {
				if(d[rt].ls) k -= d[d[rt].ls].size;
				if(!--k) return d[rt].val;
				rt = d[rt].rs;
			}
		}
	}
}T;
int32_t main(){
	cin.tie(0)->sync_with_stdio(0);
	int m, crt;
	cin >> m;
	for(int i = 1; i <= m; i++){
		int root, op, x, L, R, mid;
		cin >> root >> op >> x;
		rt[i] = rt[root];
        switch(op){
			case 1:
				T.split(rt[i], x, L, R);
				rt[i] = T.merge(T.merge(L, T.newnode(x)), R);
			break;
        	case 2:
				T.split(rt[i], x, L, mid), T.split(L, x - 1, L, R);
				R = T.merge(T.d[R].ls, T.d[R].rs);
				rt[i] = T.merge(T.merge(L, R), mid);
			break;
			case 3:
				T.split(rt[i], x - 1, L, R);
				cout << T.d[L].size + 1 << endl;
				rt[i] = T.merge(L, R);
			break;
			case 4: cout << T.kth(rt[i], x) << endl; break;
			case 5:
				T.split(rt[i], x - 1, L, R);
				if(L == 0)cout << "-2147483647\n";
				else cout << T.kth(L, T.d[L].size) << endl, rt[i] = T.merge(L, R); 
			break;
			case 6:
				T.split(rt[i], x, L, R);
				if(R == 0) cout << "2147483647\n";
				else cout << T.kth(R, 1) << endl, rt[i] = T.merge(L, R);
			break;
        }
	}
	return 0;
}

P5055 可持久化文艺平衡树

打个标记就好了。

代码

洛谷云剪贴板

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
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)
#define lowbit(x) ((x) & -(x))
#define int long long
#define eb emplace_back
constexpr int N = 3e7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
struct node{int ls, rs, rev, size, rnk;long long sum, val;}d[N];
int tot, stk[N], top;
int newnode(int val){
	int w = top ? stk[top--] : ++tot;
	d[w].size = 1, d[w].ls = d[w].rs = d[w].rev = 0;
	d[w].rnk = rd(), d[w].sum = d[w].val = val;
	return w;
}
void copynode(int&i, int j){j ? (d[i = newnode(0)] = d[j], 1) : (i = 0);}
void pushup(int x){
	d[x].sum = d[d[x].ls].sum + d[d[x].rs].sum + d[x].val;
	d[x].size = d[d[x].ls].size + d[d[x].rs].size + 1;
}
void pushdown(int x){
	int&ls = d[x].ls, &rs = d[x].rs;
	if(d[x].rev)copynode(ls, ls), copynode(rs, rs);
	if(d[x].rev)d[ls].rev ^= 1, d[rs].rev ^= 1, swap(ls, rs), d[x].rev = 0;
}
void split(int x, int k, int&L, int&R){
	if(!x)return void(L = R = 0);
	pushdown(x);
	if(d[d[x].ls].size >= k)copynode(R, x), split(d[R].ls, k, L, d[R].ls), pushup(R);
	else copynode(L, x), split(d[L].rs, k - d[d[x].ls].size - 1, d[L].rs, R), pushup(L);
}
int merge(int L, int R){
	if(!L || !R)return L + R;
	if(d[L].rnk <= d[R].rnk)return pushdown(L), d[L].rs = merge(d[L].rs, R), pushup(L), L;
	else return pushdown(R), d[R].ls = merge(L, d[R].ls), pushup(R), R;
}
int rt[201000], L, R, mid, root;
void split(int l, int r){split(root, r, L, R), split(L, l - 1, L, mid);}
void print(int x){
	if(!x)return;
	pushdown(x);
	print(d[x].ls), cout << d[x].val << " ", print(d[x].rs);
}
int32_t main(){
	cin.tie(0)->sync_with_stdio(0);
	int m, last = 0;
	cin >> m;
	FL(i, 1, m){
		int op, u, v;
		cin >> v >> op >> u;
		root = rt[v], u ^= last, L = R = mid = 0;
		if(op ^ 2)cin >> v, v ^= last;
		switch(op){
			case 1:split(root, u, L, R), rt[i] = merge(L, merge(newnode(v), R));break;
			case 2:split(u, u), stk[++top] = mid, rt[i] = merge(L, R);break;
			case 3:split(u, v), d[mid].rev ^= 1, rt[i] = merge(L, merge(mid, R));break;
			case 4:split(u, v), cout << (last = d[mid].sum) << endl, rt[i] = merge(L, merge(mid, R));
		}
	}
	return 0;
}

P5350 序列

挺烦的一道题，要定期重构，遍历完后再清空节点数，pushdown 也有新建节点。

代码

洛谷云剪贴板

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
//加上异或就可以过加强版了
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)
#define lowbit(x) ((x) & -(x))
#define eb emplace_back
#define ll long long
constexpr int mod = 1e9 + 7, M = 4e6, N = 5e5;
int addm(ll x, ll y, ll mod = mod){ll w = x + y; return (w >= mod) ? (w - mod) : w;}
#define zadd(x, y) x = addm(x, y)
mt19937 myrd(1497426);
#define rd(r) uniform_int_distribution<int>(1, r)(myrd)
int a[N];
struct node{int ls, rs, rev, size, cov, add, sum, val;}d[M];
int tot;
int newnode(int val){
	int w = ++tot;
	d[w].size = 1, d[w].add = d[w].ls = d[w].rs = d[w].rev = 0;
	d[w].sum = d[w].val = val, d[w].cov = -1;
	return w;
}
void copynode(int&i, int j){j ? (d[i = newnode(0)] = d[j], 1) : (i = 0);}
void pushup(int x){
	if(!x)return;
	d[x].sum = addm(addm(d[d[x].ls].sum, d[d[x].rs].sum), d[x].val);
	d[x].size = d[d[x].ls].size + d[d[x].rs].size + 1;
}
int build(int l, int r){
	if(l > r)return 0;
	if(l == r)return newnode(a[l]);
	int mid = l + r >> 1, z = newnode(a[mid]);
	d[z].ls = build(l, mid - 1), d[z].rs = build(mid + 1, r);
	return pushup(z), z;
}
void rev(int x){if(x)swap(d[x].ls, d[x].rs), d[x].rev ^= 1;}
void add(int x, int v){if(x)d[x].sum = addm(d[x].sum, 1LL * d[x].size * v % mod), zadd(d[x].add, v), zadd(d[x].val, v);}
void cover(int x, int v){if(x)d[x].sum = (1LL * d[x].size * v) % mod, d[x].val = d[x].cov = v, d[x].add = 0;}
void pushdown(int x){
	int&ls = d[x].ls, &rs = d[x].rs, &a = d[x].add, &cov = d[x].cov;
	if(d[x].rev || a || ~cov)copynode(ls, ls), copynode(rs, rs);
	if(d[x].rev)rev(ls), rev(rs), d[x].rev = 0;
	if(~cov)cover(ls, cov), cover(rs, cov), cov = -1;
	if(a)add(ls, a), add(rs, a), a = 0;
}
void split(int x, int k, int&L, int&R){
	if(!x)return void(L = R = 0);
	pushdown(x);
	if(d[d[x].ls].size >= k)copynode(R, x), split(d[R].ls, k, L, d[R].ls), pushup(R);
	else copynode(L, x), split(d[L].rs, k - d[d[x].ls].size - 1, d[L].rs, R), pushup(L);
}
int merge(int L, int R){
	if(!L || !R)return L + R;
	if(rd(d[L].size + d[R].size) < d[L].size)
	return copynode(L, L), pushdown(L), d[L].rs = merge(d[L].rs, R), pushup(L), L;
	else return copynode(R, R), pushdown(R), d[R].ls = merge(L, d[R].ls), pushup(R), R;
}
void split(int root, int&L, int&mid, int&R, int l, int r){
	split(root, r, L, R), split(L, l - 1, L, mid);
} 
int root, n;
int sum(int l, int r){
	int L, mid, R, ans = 0;
	split(root, L, mid, R, l, r);
	ans = d[mid].sum, root = merge(L, merge(mid, R));
	return ans;
}
void cover(int l, int r, int k){
	int L, mid, R;
	split(root, L, mid, R, l, r), copynode(mid, mid);
	cover(mid, k), root = merge(L, merge(mid, R));
}
void add(int l, int r, int k){
	int L, mid, R;
	split(root, L, mid, R, l, r), copynode(mid, mid);
	add(mid, k), root = merge(L, merge(mid, R));
}
void copy(int l1, int r1, int l2, int r2){
	int L, lm, mid, rm, R;
	if(l1 < l2)split(root, L, rm, R, l2, r2), split(L, L, lm, mid, l1, r1), copynode(rm, lm);
	else split(root, L, rm, R, l1, r1), split(L, L, lm, mid, l2, r2), copynode(lm, rm);
	root = merge(L, merge(lm, merge(mid, merge(rm, R))));
}
void swap(int l1, int r1, int l2, int r2){
	int L, lm, mid, rm, R;
	if(l1 > l2)swap(l1, l2), swap(r1, r2);
	split(root, L, rm, R, l2, r2), split(L, L, lm, mid, l1, r1);
	root = merge(L, merge(rm, merge(mid, merge(lm, R))));
}
void revers(int l, int r){
	int L, mid, R;
	split(root, L, mid, R, l, r), copynode(mid, mid);
    rev(mid), root = merge(L, merge(mid, R));
}
void dfs(int x){
	if(!x)return;
	pushdown(x);
	dfs(d[x].ls), a[++n] = d[x].val, dfs(d[x].rs);
}
int32_t main(){
	cin.tie(0)->sync_with_stdio(0);
	long long m, last = 0;
	cin >> n >> m;
	FL(i, 1, n)cin >> a[i];
	root = build(1, n);
	FL(i, 1, m){
		long long op, l1, l2 = 0, r1, r2 = 0;
		cin >> op >> l1 >> r1;
		if(op >= 2 && op <= 5)cin >> l2;
		if(op >= 4 && op <= 5)cin >> r2; 
		switch(op){
			case 1:cout << (last = sum(l1, r1)) << endl;break;
			case 2:cover(l1, r1, l2);break;
			case 3:add(l1, r1, l2);break;
			case 4:copy(l1, r1, l2, r2);break;
			case 5:swap(l1, r1, l2, r2);break;
			case 6:revers(l1, r1);
		}
		if(tot > 2e6)n = 0, dfs(root), tot = 0, root = build(1, n);
	}
	n = 0, dfs(root);
	FL(i, 1, n)cout << a[i] << " ";
	return 0;
}

更新于：2025年1月8日

平衡树

treap