数据结构

线段树

线段树合并

原理

线段树合并是将多颗线段树合并成一颗线段树。
合并的时候，将重合的节点值相加，不重合的节点保持原样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int merge(int p1, int p2, int l, int r) {
	if(p1 == 0 || p2 == 0) {
		return p1 + p2;
	}
	if(l == r) {
		nod[p1].mx = nod[p1].mx + nod[p2].mx; 
		nod[p1].ans = l;
		return p1;
	}
	int mid = (l + r) / 2;
	ls[p1] = merge(ls[p1], ls[p2], l, mid);
	rs[p1] = merge(rs[p1], rs[p2], mid + 1, r);
	pushup(p1);
	return p1;
}

时间复杂度

线段树 $T_1, T_2,…, T_n$ 将它们以任意顺序合并的时间复杂度为 $O(\sum_{i = 1}^n |T_i| - \sum_{i = 1}^n - |\sum_{i = 1}^n T_i|)$，其中 $|T_i|$ 是线段树节点的数量,可以用数学归纳法证明。

推论：值域为 $N$ 的若干线段树一共进行过 $k$ 次插入操作， 合并它们的时间复杂度为 $O(k\cdot\log N - |\sum_{i = 1}^n T_i|) \leq O(k\cdot \log N)$

例题 CF600E

CF600E Lomsat gelral


我们可以在每一个节点上开一个动态开点权值线段树，对于每颗线段树，我们可以维护最多颜色有多少个，颜色最多的颜色编号的之和。把子节点的信息通过线段树合并传送到父节点，从而获得每个节点子树主导地位的颜色编号和。

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
#include <iostream>
#include <vector>

using namespace std;
using i64 = long long;

const int maxn1 = 1e7 + 5;
const int maxn2 = 1e7 + 5;

int ls[maxn1], rs[maxn1], cnt = 0;

struct node {
	i64 mx, ans;
	node operator + (node x) {
		if(mx == x.mx) {
			return (node){x.mx, ans + x.ans};
		}
		else if(mx > x.mx){
			return (node){mx, ans};
		}
		else {
			return (node){x.mx, x.ans};
		}
	}
}nod[maxn1];

void pushup(int u) {
	nod[u] = nod[ls[u]] + nod[rs[u]];
}

void pushdown(int u) {
	if(!ls[u])
		ls[u] = ++cnt;
	if(!rs[u]) 
		rs[u] = ++cnt;
}

int a[maxn2];

void update(int L, int R, int l, int r, int u) {
	if(l == r) {
		nod[u].mx++;
		nod[u].ans = l;
		return;
	} 
	pushdown(u);
	int mid = (l + r) / 2;
	if(L <= mid) {
		update(L, R, l, mid, ls[u]);
	}
	if(R > mid) {
		update(L, R, mid + 1, r, rs[u]);
	}
	pushup(u);
}

i64 query(int u) {
	return nod[u].ans;
}

vector<int> e[maxn2];
void add(int u, int v) {
	e[u].push_back(v);
	e[v].push_back(u);
}

int merge(int p1, int p2, int l, int r) {
	if(p1 == 0 || p2 == 0) {
		return p1 + p2;
	}
	if(l == r) {
		nod[p1].mx = nod[p1].mx + nod[p2].mx; 
		nod[p1].ans = l;
		return p1;
	}
	int mid = (l + r) / 2;
	ls[p1] = merge(ls[p1], ls[p2], l, mid);
	rs[p1] = merge(rs[p1], rs[p2], mid + 1, r);
	pushup(p1);
	return p1;
}

int head[maxn2], n;

void dfs(int u, int fa) {
	update(a[u], a[u], 1, n, u);
	for(auto v : e[u]) {
		if(v == fa)
			continue;
		dfs(v, u);
		merge(u, v, 1, n);
	}
} 

int main() {
	cin >> n;
	cnt = n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
	}
	dfs(1, 0);
	for(int i = 1; i <= n; i++) {
		cout << query(i) << ' ';
	}
	return 0;
}

例题 P3224

P3224 [HNOI2012] 永无乡

首先对于连通性，我们很自然的想到用并查集维护。然后，思考一下如何查询排名第 $k$ 小的方案，我们知道全局第 $k$ 小我们可以用权值线段树来维护，于是我们只需要在并查集的同时，进行线段树合并就可以了。

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
#include <iostream>

using i64 = long long;
using namespace std;

const int maxn = 1e6;

int ls[maxn], rs[maxn], nod[maxn], a[maxn], fa[maxn], cnt, n;

int find(int u) {
	if(u == fa[u]) {
		return u;
	}
	return fa[u] = find(fa[u]);
}

void pushdown(int u) {
	if(!ls[u]) {
		ls[u] = ++cnt;
	}
	if(!rs[u]) {
		rs[u] = ++cnt;
	}
}

void pushup(int u) {
	nod[u] = nod[ls[u]] + nod[rs[u]];
}

void update(int x, int l, int r, int u) {
	if(l == r) {
		nod[u] = 1;
		return;
	}
	pushdown(u);
	int mid = (l + r) / 2;
	if(x <= mid) {
		update(x, l, mid, ls[u]);
	}
	else {
		update(x, mid + 1, r, rs[u]);
	}
	pushup(u);
}

int query(int l, int r, int u, int k) {
	if(nod[u] < k) {
		return -1;
	}
	if(l == r) {
		return a[l];
	}
	int mid = (l + r) / 2;
	if(nod[ls[u]] >= k) {
		return query(l, mid, ls[u], k);
	}
	else {
		return query(mid + 1, r, rs[u], k - nod[ls[u]]);
	}
}

int merge(int u, int v, int l, int r) {
	if(!u || !v) {
		return u + v;
	}
	if(l == r) {
		nod[u] = nod[u] + nod[v];
		return u;
	}
	int mid = (l + r) / 2;
	ls[u] = merge(ls[u], ls[v], l, mid);
	rs[u] = merge(rs[u], rs[v], mid + 1, r);
	pushup(u);
	return u;
}

void uset(int u, int v) {
	u = find(u);
	v = find(v);
	if(u != v) {
		fa[u] = v;
		merge(v, u, 1, n);
	}
}

int main() {
	int m;
	cin >> n >> m;
	cnt = n;
	for(int i = 1; i <= n; i++) {
		fa[i] = i;
	}
	for(int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		a[x] = i;
		update(x, 1, n, i);
	}
	for(int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		uset(u, v);
	}
	int q;
	cin >> q;
	while(q--) {
		char c;
		int x, y;
		cin >> c >> x >> y;
		if(c == 'Q') {
			cout << query(1, n, find(x), y) << endl;
		}
		if(c == 'B') {
			uset(x, y);
		}
	}
	return 0;
}

例题 P4556

P4556 [Vani有约会] 雨天的尾巴 /【模板】线段树合并

操作是向树上某个的每一个节点放一个 $z$ 类型的救济粮，我们可以想到树上差分，在路径 $u \rightarrow v$ 上放一袋救济粮，等价于在差分后，在 $u$ 和 $v$ 上放一袋，在 $lca(u, v)$ 和 $fa(lca(u, v))$上拿走一袋。然后，我们可以用权值线段树来维护存放最多的救济粮是哪个，然后用线段树合并来得到差分后子树的存放最多的救济粮是哪个，也就是 $i$ 号屋的救济粮。注意，处理0的时候需要小心。

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
#include <iostream>
#include <vector>
using i64 = long long;
using namespace std;

const int maxn = 1e7 + 1e6;
const int maxn2 = 1e5 + 5;
const int maxz = 1e5;

vector<int> e[maxn2];

struct node {
	int id, mx;
	node operator + (node nod) {
		if(mx < nod.mx) {
			return nod;
		}
		else {
			return (*this);
		}
	}
}nod[maxn];

int ls[maxn], rs[maxn], ans[maxn2], cnt, fa[maxn2][20], dep[maxn2], n;

void pushdown(int u) {
	if(!ls[u]){
		ls[u] = ++cnt;
	}
	if(!rs[u]) {
		rs[u] = ++ cnt;
	}
}

void pushup(int u) {
	nod[u] = nod[ls[u]] + nod[rs[u]];
}

void update(int x, int l, int r, int u, int k) {
	if(l == r) {
		nod[u] = (node){x, nod[u].mx + k};
		if(nod[u].mx <= 0) {
			nod[u].id = 0;
		}
		return;
	}
	pushdown(u);
	int mid = (l + r) / 2;
	if(x <= mid) {
		update(x, l, mid, ls[u], k);
	}
	else {
		update(x, mid + 1, r, rs[u], k);
	}
	pushup(u);
}

int query(int u) {
	return nod[u].id;
}

int merge(int u, int v, int l, int r) {
	if(!u || !v) {
		return u + v;
	}
	if(l == r) {
		nod[u].mx += nod[v].mx;
		nod[u].id = max(nod[u].id, nod[v].id);
		if(nod[u].mx == 0)
		    nod[u].id = 0;
		return u;
	}
	int mid = (l + r) / 2;
	ls[u] = merge(ls[u], ls[v], l, mid);
	rs[u] = merge(rs[u], rs[v], mid + 1, r);
	pushup(u);
	return u;
}

void add(int u, int v) {
	e[u].push_back(v);
	e[v].push_back(u);
}

void dfs1(int u, int f) {
	fa[u][0] = f;
	dep[u] = dep[f] + 1;
	for(auto v : e[u]) {
		if(v == f)
			continue;
		dfs1(v, u);
	} 
}

void init() {
	for(int i = 1; i < 20; i++) {
		for(int u = 1; u <= n; u++) {
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		}
	}
}

int lca(int u, int v) {
	if(dep[u] < dep[v]) {
		swap(u, v);
	}
	for(int i = 19; i >= 0; i--) {
		if(dep[fa[u][i]] >= dep[v])
			u = fa[u][i];
	}
	if(u == v) {
		return u;
	}
	for(int i = 19; i >= 0; i--) {
		if(fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	}
	return fa[u][0];
}

void dfs2(int u, int f) {
	for(auto v : e[u]) {
		if(v == f)
			continue;
		dfs2(v, u);
		merge(u, v, 1, maxz);

	}
	ans[u] = nod[u].id;
}

int main() {
	int m;
	cin >> n >> m;
	cnt = n;
	for(int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
	}
	dfs1(1, 0);
	init();
	while(m--) {
		int x, y, z;
		cin >> x >> y >> z;
		update(z, 1, maxz, x, 1);
		update(z, 1, maxz, y, 1);		
		update(z, 1, maxz, lca(x, y), -1);
		update(z, 1, maxz, fa[lca(x, y)][0], -1);
	}
	dfs2(1, 0);
	for(int i = 1; i <= n; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

2 参考资料

算法学习笔记(88): 线段树合并 Pecco