平衡树

发表于 更新于 分类于 ， ， ， 阅读次数： 本文字数： 2.5k 阅读时长 ≈ 9 分钟

平衡树

全称是二叉搜索平衡树

二叉搜索树：对于一棵二叉树，每个节点有权值 valval，任意节点 xx 的左子树的权值小于等于 valxval_x，右子树反之。

二叉搜索树的优点：

  1. 具有单调性，可以 log2log_2 的时间查找。
  2. 二叉搜索树的中序遍历是单调不减的，可以将下标当做权值，这样一个序列可以映射到一棵二叉搜索树。

为什么需要平衡树？

  • 一个序列对应的二叉搜索树不唯一。我们希望找到高度最小的那颗应用。

若一棵二叉树的任意一个结点 xx，其左右子树高度差不超过 11，称为二叉平衡树。

算法竞赛领域常用的平衡树：

  1. treap
  2. splay
  3. fhq_treap

其中，treap 和 fhq_treap 利用的是随机平衡，不追求绝对平衡。splay 是贪心策略平衡。treap 和 splay 都是通过旋转改变形态，fhq_treap 通过分裂和合并来改变形态。

Fhq_treap 实现

  1. 分裂操作

    将一棵平衡树分裂成 aa 和 bb 两棵子树，且 vala≤val,valb>valval_a\le val,val_b>val。valval 是选取的某个数。

    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
    struct node {
    	int val, l, r, size, rnk;
    }tree[N];
    void update(int cur)
    {
    	tree[cur].size = tree[tree[cur].l].size + tree[tree[cur].r].size + 1;
    	return;
    }
    void split(int cur, int& a, int& b, int val)
    {
    	if (!cur)
    	{
    		a = b = 0;
    		return;
    	}
    	if (tree[cur].val <= val)
    	{
    		a = cur;
    		split(tree[cur].r, tree[cur].r, b, val);
    	}
    	else
    	{
    		b = cur;
    		split(tree[cur].l, a, tree[cur].l, val);
    	}
    	update(cur);
    	return;
    }

  2. 合并操作

    将 a,ba,b 两棵平衡树合并，且 aa 平衡树的任意权值一定小于等于 bb 平衡树的任意权值。

模板完整代码：

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
#include<bits/stdc++.h>
typedef int int32;
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, root, cnt;
struct node {
	int val, l, r, size, rnk;
}tree[N];
void update(int cur)
{
	tree[cur].size = tree[tree[cur].l].size + tree[tree[cur].r].size + 1;
	return;
}
int add_node(int val)
{
	tree[++cnt] = { val,0,0,1,rand() };
	return cnt;
}
void split(int cur, int& a, int& b, int val)
{
	if (!cur)
	{
		a = b = 0;
		return;
	}
	if (tree[cur].val <= val)
	{
		a = cur;
		split(tree[cur].r, tree[cur].r, b, val);
	}
	else
	{
		b = cur;
		split(tree[cur].l, a, tree[cur].l, val);
	}
	update(cur);
	return;
}
void merge(int& cur, int a, int b)//合并
{
	if (!a || !b)
	{
		cur = a + b;
		return;
	}
	if (tree[a].rnk <= tree[b].rnk)
	{
		cur = a;
		merge(tree[a].r, tree[a].r, b);
	}
	else
	{
		cur = b;
		merge(tree[b].l, a, tree[b].l);
	}
	update(cur);
	return;
}
void insert(int& cur, int val)//插入
{
	int a = 0, b = 0, c = add_node(val);
	split(cur, a, b, val);
	merge(a, a, c);
	merge(cur, a, b);
	return;
}
void del(int& cur, int val)//输出
{
	int a = 0, b = 0, c = 0;
	split(cur, a, b, val);
	split(a, a, c, val - 1);
	merge(c, tree[c].l, tree[c].r);
	merge(a, a, c);
	merge(cur, a, b);
	return;
}
int find_num(int cur, int x)//寻找第 $x$ 个元素
{
	while (tree[tree[cur].l].size + 1 != x)
		if (tree[tree[cur].l].size >= x)
			cur = tree[cur].l;
		else
		{
			x -= tree[tree[cur].l].size + 1;
			cur = tree[cur].r;
		}
	return tree[cur].val;
}
int find_rank(int& cur, int val)//寻找 $val$ 的第一个位置
{
	int a = 0, b = 0;
	split(cur, a, b, val - 1);
	int tmp = tree[a].size + 1;
	merge(cur, a, b);
	return tmp;
}
int prev(int& cur, int val)//寻找前驱
{
	int a = 0, b = 0;
	split(cur, a, b, val - 1);
	int tmp = find_num(a, tree[a].size);
	merge(cur, a, b);
	return tmp;
}
int suf(int& cur, int val)//寻找后继
{
	int a = 0, b = 0;
	split(cur, a, b, val);
	int tmp = find_num(b, 1);
	merge(cur, a, b);
	return tmp;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	srand(time(0));
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int opt, val;
		cin >> opt >> val;
		if (opt == 1)
			insert(root, val);
		else if (opt == 2)
			del(root, val);
		else if (opt == 3)
			cout << find_rank(root, val) << '\n';
		else if (opt == 4)
			cout << find_num(root, val) << '\n';
		else if (opt == 5)
			cout << prev(root, val) << '\n';
		else
			cout << suf(root, val) << '\n';
	}
	return 0;
}

例题

洛谷P1486

P1486 郁闷的出纳员

NOI2004 的题。

第一行有两个整数 nn 和 min⁡\min。nn 表示下面有多少条命令，min⁡\min 表示工资下界。

接下来的 nn 行，每行一个字符 xx 和一个整数 kk，表示一条命令。命令可以是以下四种之一：

  • I k 新建一个工资档案，初始工资为 kk。如果某员工的初始工资低于工资下界，他将立刻离开公司。
  • A k 把每位员工的工资加上 kk。
  • S k 把每位员工的工资扣除 kk。
  • F k 查询第 kk 多的工资。

在初始时，可以认为公司里一个员工也没有。

维护一个全局懒标记，懒标记减的时候删除离开的人。

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
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	srand(time(0));
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		char c;
		int x;
		cin >> c >> x;
		if (c == 'I')
			if (x >= m)
				insert(root, x - tag);
			else
				;
		else if (c == 'A')
			tag += x;
		else if (c == 'S')
		{
			tag -= x;
			while (root && find_num(root, 1) + tag < m)
				del(root, find_num(root, 1)), sum++;
		}
		else
			if (!root || tree[root].size < x)
				cout << "-1\n";
			else
				cout << find_num(root, tree[root].size - x + 1) + tag << '\n';
	}
	cout << sum;
	return 0;
}

洛谷P2234

P2234 营业额统计

而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。

我们定义，一天的最小波动值 = min⁡{∣该天以前某一天的营业额−该天营业额∣}\min\{|\text{该天以前某一天的营业额}-\text{该天营业额}|\}。

特别地，第一天的最小波动值为第一天的营业额。

和前驱后继减，即可保证最小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	srand(time(0));
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		insert(root, x);
		if (i == 1)
			sum += x;
		else if (tree[root].size == find_rank(root, x))
			sum += abs(prev(root, x) - x);
		else if (find_rank(root, x) == 1)
			sum += abs(suf(root, x) - x);
		else
			sum += min(abs(prev(root, x) - x), abs(suf(root, x) - x));
	}
	cout << sum;
	return 0;
}

洛谷P3224

P3224 永无乡

永无乡包含 nn 座岛，编号从 11 到 nn ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 nn 座岛排名，名次用 11 到 nn 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 aa 出发经过若干座（含 00 座）桥可以 到达岛 bb ，则称岛 aa 和岛 bb 是连通的。

现在有两种操作：

B x y 表示在岛 xx 与岛 yy 之间修建一座新桥。

Q x k 表示询问当前与岛 xx 连通的所有岛中第 kk 重要的是哪座岛，即所有与岛 xx 连通的岛中重要度排名第 kk 小的岛是哪座，请你输出那个岛的编号。

使用并查集+平衡树，合并使用启发式合并，即拆小的往大的上 merge。

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
int find(int x)
{
	if (x == fa[x])
		return x;
	return fa[x] = find(fa[x]);
}
void dfs(int x, int& y)
{
	if (!x)
		return;
	int a = 0, b = 0, c = x, val = tree[x].val;
	int l = tree[x].l, r = tree[x].r;
	tree[x].l = tree[x].r = 0;
	split(y, a, b, val);
	merge(a, a, c);
	merge(y, a, b);
	dfs(l, y);
	dfs(r, y);
	return;
}
void unionn(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x != y)
		if (tree[root[x]].size <= tree[root[y]].size)
		{
			fa[x] = y;
			dfs(root[x], root[y]);
		}
		else
		{
			swap(x, y);
			fa[x] = y;
			dfs(root[x], root[y]);
		}
	return;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	srand(time(0));
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i], b[a[i]] = i, fa[i] = i, root[i] = i,
		tree[i] = { a[i],0,0,1,rand() };
	cnt = n;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		unionn(x, y);
	}
	cin >> q;
	while (q--)
	{
		char c;
		int x, y;
		cin >> c >> x >> y;
		if (c == 'B')
			unionn(x, y);
		else
			if (tree[root[find(x)]].size < y)
				cout << "-1\n";
			else
				cout << b[find_num(root[find(x)], y)] << '\n';
	}
	return 0;
}

洛谷P6136

P6136 【模板】普通平衡树（数据加强版）

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
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	srand(time(0));
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		int x;
		cin >> x;
		insert(root, x);
	}
	for(int i = 1; i <= m; i++)
	{
		int opt, val;
		cin >> opt >> val;
		val ^= last;
		if(opt == 1)
			insert(root, val);
		else if(opt == 2)
			del(root, val);
		else if(opt == 3)
			ans ^= (last = find_rank(root, val));
		else if(opt == 4)
			ans ^= (last = find_num(root, val));
		else if(opt == 5)
			ans ^= (last = prev(root, val));
		else
			ans ^= (last = suf(root, val));
	}
	cout << ans;
	return 0;
}

文艺平衡树（fhq_treap 版）

需要区间反转时，为了实现区间翻转，我们使用懒标记（lazy tag），像线段树一样。

  • pushdown 函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void pushdown(int cur)
    {
    	if (!tree[cur].tag)
    		return;
    	swap(tree[cur].l, tree[cur].r);
    	tree[tree[cur].l].tag ^= 1;
    	tree[tree[cur].r].tag ^= 1;
    	tree[cur].tag = 0;
    	return;
    }

  • split 函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    void split(int cur, int& a, int& b, int val)
    {
    	if (!cur)
    	{
    		a = b = 0;
    		return;
    	}
    	pushdown(cur);
    	if (tree[tree[cur].l].size + 1 <= val)//文艺平衡树是按size分的
    	{
    		a = cur;
    		split(tree[cur].r, tree[cur].r, b, val - tree[tree[cur].l].size - 1);
    	}
    	else
    	{
    		b = cur;
    		split(tree[cur].l, a, tree[cur].l, val);
    	}
    	update(cur);
    	return;
    }

  • merge 函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    void merge(int& cur, int a, int b)
    {
    	if (!a || !b)
    	{
    		cur = a + b;
    		return;
    	}
    	if (tree[a].rnk <= tree[b].rnk)
    	{
    		pushdown(a);
    		cur = a;
    		merge(tree[a].r, tree[a].r, b);
    	}
    	else
    	{
    		pushdown(b);
    		cur = b;
    		merge(tree[b].l, a, tree[b].l);
    	}
    	update(cur);//记得update，forget to update 3 times
    	return;
    }

  • reverse 函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void reverse(int& cur, int x, int y)
    {
    	int a = 0, b = 0, c = 0;
    	split(cur, a, b, y);
    	split(a, a, c, x - 1);
    	tree[c].tag ^= 1;
    	merge(a, a, c);
    	merge(cur, a, b);
    	return;
    }

  • print 函数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void print(int x)
    {
    	if (!x)
    		return;
    	pushdown(x);
    	print(tree[x].l);
    	cout << tree[x].val << ' ';
    	print(tree[x].r);
    	return;
    }

例题

洛谷P3391

P3391 【模板】文艺平衡树 - 洛谷

洛谷P3850

P3850 书架

Knuth 先生家里有个精致的书架，书架上有 N 本书，如今他想学到更多的知识，于是又买来了 M 本不同的新书。现在他要把新买的书依次插入到书架中，他已经把每本书要插入的位置标记好了，并且相应的将它们放好。由于 Knuth 年龄已大，过几天他已经记不清某些位置上放的到底是什么书了，请问你能帮助他吗？

文艺平衡树加一个 string 就可以了

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
struct node {
	int val, l, r, size, rnk, tag;
	string s;
}tree[N];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	srand(time(0));
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> s;
		int a = add_node(i);
		tree[a].s = s;
		merge(root, root, a);
	}
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		int x;
		cin >> s >> x;
		int a = 0, b = 0, c = add_node(x);
		tree[c].s = s;
		split(root, a, b, x);
		merge(a, a, c);
		merge(root, a, b);
	}
	cin >> m;
	for (int i = 1; i <= m; i++)
	{
		int x;
		cin >> x;
		int a = 0, b = 0, c = 0;
		split(root, a, b, x + 1);
		split(a, a, c, x);
		cout << tree[c].s << '\n';
		merge(a, a, c);
		merge(root, a, b);
	}
	return 0;
}