# Road Map
# 线段树
线段树用于解决 RMQ(Range Minimum/Maximum Query) 问题，即区间最值问题
比如在对数时间内从数组中找到最小值、最大值、总和、最大公约数、最小公倍数等。
相关问题：
- 一个数组，求任意一个区间的最大的数是多少
- 一个数组，求任意一个区间的和为多少
- 修改某个元素后，如何支持上述查询
# 线段树和 ST 表时间复杂度
- 线段树：O(NlogN)预处理，单词询问 O(logN)
- ST 表：O(NlogN)预处理，单词询问 O(1)
# 求区间和
const int N = 1e5 + 1;
int tree[N] = {0};
int arr[N] = {0};
void build_tree(int node, int start, int end) { // 构建[start, end]区间
if (start == end) {
tree[node] = arr[start];
return;
}
int mid = start + end >> 1;
int left_node = 2 * node + 1;
int right_node = 2 * node + 2;
build_tree(left_node, start, mid);
build_tree(right_node, mid + 1, end);
tree[node] = tree[left_node] + tree[right_node];
}
void update_tree(int node, int start, int end, int idx, int val) { // 更新 idx 的值
if (start == end) {
arr[idx] = val;
tree[node] = val;
return;
}
int mid = start + end >> 1;
int left_node = 2 * node + 1;
int right_node = 2 * node + 2;
if (idx >= start && idx <= mid) {
update_tree(left_node, start, mid, idx, val);
} else {
update_tree(right_node, mid + 1, end, idx, val);
}
tree[node] = tree[left_node] + tree[right_node];
}
int query(int node, int start, int end, int L, int R) { // 查询[L, R]区间
printf("start = %d, end = %d \n", start, end);
if (R < start || L > end) return 0; // 区间外
if (L <= start && end <= R) return tree[node]; // 区间内
if (start == end) return tree[node]; // 叶子节点
int mid = start + end >> 1;
int left_node = 2 * node + 1;
int right_node = 2 * node + 2;
int val_left = query(left_node, start, mid, L, R);
int val_right = query(right_node, mid + 1, end, L, R);
return val_left + val_right;
}
int main() {
int n = 6;
for (int i = 0; i < n; i++) {
arr[i] = 2 * i + 1;
}
build_tree(0, 0, n - 1);
int floor = 4; // 层数；如何计算？
for (int i = 0; i < pow(2, 4); i++) {
printf("tree[%d] = %d \n", i, tree[i]);
}
cout << endl;
update_tree(0, 0, n - 1, 4, 6);
for (int i = 0; i < pow(2, 4); i++) {
printf("tree[%d] = %d \n", i, tree[i]);
}
cout << endl;
int s = query(0, 0, n - 1, 2, 5);
printf("s = %d\n", s);
return 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
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
# 课程讲解
- https://www.bilibili.com/video/av47331849
- https://www.acwing.com/blog/content/514/