线段树是一种特殊的数据结构，它可以在 $O(\log n)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
最简单的线段树的构建：
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
#include <iostream>
#include <vector>
using namespace std;
// 定义线段树的节点
struct Node {
int l, r; // 左右子节点的下标
int sum; // 区间和
};
vector<Node> tree; // 存储线段树的数组
// 构建线段树
void build(int l, int r, int index, vector<int>& nums) {
tree[index].l = l;
tree[index].r = r;
if (l == r) { // 叶子节点
tree[index].sum = nums[l];
return;
}
int mid = (l + r) / 2;
build(l, mid, index * 2, nums); // 构建左子树
build(mid + 1, r, index * 2 + 1, nums); // 构建右子树
tree[index].sum = tree[index * 2].sum + tree[index * 2 + 1].sum; // 计算区间和
}
// 区间查询
int query(int l, int r, int index) {
if (tree[index].l >= l && tree[index].r <= r) { // 当前区间完全包含在查询区间内
return tree[index].sum;
}
int mid = (tree[index].l + tree[index].r) / 2;
int sum = 0;
if (l <= mid) { // 查询区间和左子树有交集
sum += query(l, r, index * 2);
}
if (r > mid) { // 查询区间和右子树有交集
sum += query(l, r, index * 2 + 1);
}
return sum;
}
// 单点修改
void update(int pos, int val, int index) {
if (tree[index].l == tree[index].r) { // 叶子节点
tree[index].sum = val;
return;
}
int mid = (tree[index].l + tree[index].r) / 2;
if (pos <= mid) { // 修改的位置在左子树
update(pos, val, index * 2);
} else { // 修改的位置在右子树
update(pos, val, index * 2 + 1);
}
tree[index].sum = tree[index * 2].sum + tree[index * 2 + 1].sum; // 更新区间和
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // 原始数组
int n = nums.size(); // 数组长度
tree.resize(n * 4); // 线段树的大小为 4n
build(0, n - 1, 1, nums); // 构建线段树
cout << query(0, 4, 1) << endl; // 查询区间 [0, 4] 的和
update(2, 10, 1); // 将第 2 个元素修改为 10
cout << query(0, 4, 1) << endl; // 查询区间 [0, 4] 的和
return 0;
}
构建解释：
递归地将数组分为左右两个子数组，直到子数组长度为 1，此时该子数组的区间和就是该子数组的元素值。
查询解释：
如果当前区间完全包含在查询区间内，则直接返回该区间的区间和。
如果当前区间和查询区间有交集，则递归地查询左子树和右子树，然后将它们的区间和相加。
修改解释：
如果当前区间的左右端点都等于修改的位置，则直接将该区间的区间和修改为新的值。
如果当前区间和修改的位置有交集，则递归地修改左子树和右子树，然后更新当前区间的区间和。
线段树的时间复杂度：
线段树的时间复杂度主要取决于查询和修改操作的次数。
查询操作的时间复杂度为 $O(\log n)$，因为每次查询都可以将查询区间缩小一半。
修改操作的时间复杂度为 $O(\log n)$，因为每次修改都可以将修改的位置缩小一半。
因此，线段树的时间复杂度为 $O(\log n)$。
线段树的空间复杂度：
线段树的空间复杂度主要取决于数组的大小。
如果数组的大小为 $n$，则线段树的空间复杂度为 $O(4n)$。
因此，线段树的空间复杂度为 $O(n)$。
线段树的优点：
-
可以在 $O(\log n)$ 的时间复杂度内实现单点修改、区间修改、区间查询等操作。
-
可以支持动态修改，即可以在修改数组的同时，在线地查询修改后的数组。
-
可以支持区间合并，即可以将多个区间的信息合并成一个区间的信息。
-
可以支持区间分裂，即可以将一个区间分裂成多个区间。
线段树的缺点：
-
线段树的空间复杂度较高，需要 $O(4n)$ 的空间。
-
线段树的实现较为复杂，需要递归地构建线段树和查询线段树。
-
线段树的查询和修改操作的时间复杂度较高，需要 $O(\log n)$ 的时间。
-
线段树的查询和修改操作的实现较为复杂，需要递归地查询和修改线段树。
参考
