线段树是一种特殊的数据结构，它可以在 $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)$ 的时间。

  • 线段树的查询和修改操作的实现较为复杂，需要递归地查询和修改线段树。

参考