线段树是一种用于存储区间或段的树形数据结构，使得在其上进行快速的查询和修改操作成为可能。它常用于处理涉及区间的查询问题，如求区间和、区间最小值、区间最大值等。

基本概念

线段树是一棵二叉树，主要用于高效地解决一类区间查询问题。其每个节点表示一个区间，叶节点表示数组中的单个元素，内部节点表示其子节点区间的并集。

线段树的结构

  • 叶节点：叶节点对应数组的单个元素。
  • 内部节点：每个内部节点表示其子节点所代表的区间的并集。

例如，给定数组 [1, 3, 5, 7, 9, 11]，其线段树的结构如下：

1
2
3
4
5
6
7
                   [0, 5]
                  /       \
           [0, 2]         [3, 5]
          /      \        /      \
      [0, 1]   [2, 2]  [3, 4]   [5, 5]
     /     \           /    \
[0, 0]   [1, 1]   [3, 3]  [4, 4]

构建线段树

线段树的构建时间复杂度为 O(n)，其中 n 是数组的长度。构建过程如下：

  1. 递归分割区间：从数组的中间分割，将数组分为左右两个区间。
  2. 构建子树：对左右区间分别构建线段树。
  3. 计算节点值：内部节点的值由其左右子节点的值计算得到。

一般建树代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
void buildTree(LL k, LL l, LL r){
    if (l == r) {
        node[k].val = arr[l];
        node[k].left = l;
        node[k].right = r;
        return;
    }
    node[k].left = l; node[k].right = r;
    LL mid =  l + (r - l) / 2;
    buildTree(k*2, l, mid);
    buildTree(k*2+1, mid+1, r);
    node[k].val = node[k*2].val + node[k*2+1].val;
}

线段树的操作

  1. 单点/区间查询：查询某一范围内的数据，如区间和、区间最小值等。
  2. 单点/区间更新：更新数组中的某个/区间元素，并更新相关区间的信息。

一般在线段树中会实现如下函数：

  • query(left, right) 方法用于查询 [left, right] 区间的和。
  • update(index, value) 方法用于更新数组中 index 位置的值，并更新相关区间的信息。
  • pushDown(k)用于下放节点k上的lazyTag

上述代码实现见下面应用部分的例题。

线段树的应用

线段树广泛应用于解决以下问题：

  • 区间求和
  • 区间最小值/最大值查询
  • 区间更新操作
  • 动态顺序统计

通过线段树，可以在 O(log n) 时间复杂度内完成区间查询和更新操作，使其在处理动态数组问题时非常高效。

例题1：【模板】线段树1

题目传送门：P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

线段树区间修改+区间查询模板题，实现代码如下：

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
/**********************************************************************************************************************
 * Problem: P3372 【模板】线段树 1
 * URL: https://www.luogu.com.cn/problem/P3372
 * Description: Segment Tree（区间修改，区间查询）
 * Created by Vegetabot on 6/7/2024.
**********************************************************************************************************************/
#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
LL n,m,root=1;
vector<LL> arr(N);
struct TreeNode{
    LL val, add, left, right;
    TreeNode() : val(0), add(0), left(-1), right(-1) {}
};
vector<TreeNode> node(N*3);
void buildTree(LL k, LL l, LL r){
    if (l == r) {
        node[k].val = arr[l];
        node[k].left = l;
        node[k].right = r;
        return;
    }
    node[k].left = l; node[k].right = r;
    LL mid =  l + (r - l) / 2;
    buildTree(k*2, l, mid);
    buildTree(k*2+1, mid+1, r);
    node[k].val = node[k*2].val + node[k*2+1].val;
}
void addTag(LL k, LL val){
    node[k].val += val * (node[k].right - node[k].left + 1);
    node[k].add += val;
}
void pushDown(LL k){
    addTag(k*2, node[k].add);
    addTag(k*2+1, node[k].add);
    node[k].add = 0;
}
void modify(LL k, LL l, LL r, LL val){
    if (l <= node[k].left && node[k].right <= r) {
        addTag(k, val);
        return;
    }
    pushDown(k);
    LL mid = node[k].left + (node[k].right - node[k].left)/2;
    if (l<=mid) modify(k*2, l, r, val);
    if (r>mid) modify(k*2+1, l, r, val);
    node[k].val = node[k*2].val + node[k*2+1].val;
}
LL query(LL k, LL l, LL r){
    if (l <= node[k].left && node[k].right <= r) {
        return node[k].val;
    }
    pushDown(k);
    LL mid = node[k].left + (node[k].right - node[k].left)/2, res = 0;
    if (l <= mid)  res += query(k*2, l, r);
    if (r > mid) res += query(k*2+1, l, r);
    return res;
}
int main() {
    cin >> n >> m;
    for(int i=1; i<=n; ++i){
        scanf("%lld", &arr[i]);
    }
    buildTree(root, 1, n);
    for(int i=1; i<=m; ++i) {
        LL op, a, b, c;
        scanf("%lld", &op);
        if (op == 1) {
            scanf("%lld%lld%lld", &a, &b, &c);
            modify(root, a, b, c);
        } else {
            scanf("%lld%lld", &a, &b);
            printf("%lld\n", query(root, a, b));
        }
    }
    return 0;
}

例题2：【模板】线段树2

题目传送门：P3373 【模板】线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

此题同样是线段树区间修改+区间查询模板题，相比上一道模板题，难度主要加在了如何打lazyTag上，本题涉及两种lazyTag（乘法，加法），解决这道题只需牢记下放lazyTag时严格遵循先乘后加即可。

实现代码如下：

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
/**********************************************************************************************************************
 * Problem: P3373 【模板】线段树 2
 * URL: https://www.luogu.com.cn/problem/P3373
 * Description: Segment Tree
 * Created by Vegetabot on 6/8/2024.
**********************************************************************************************************************/
#include<bits/stdc++.h>
#define N 100003
#define LL long long 
using namespace std;
LL n, q, m, root=1;
vector<LL> arr(N);
struct TreeNode{
    LL val, add, multi, left, right;
    TreeNode(): val(0), add(0), multi(1), left(-1), right(-1) {}
};
vector<TreeNode> node(N*3);
void buildTree(LL k, LL l, LL r){
    node[k].left = l; node[k].right = r;
    if (l == r) {
        node[k].val = arr[l];
        return;
    }
    LL mid = l + (r - l) / 2;
    buildTree(k*2, l, mid);
    buildTree(k*2+1, mid+1, r);
    node[k].val = node[k*2].val + node[k*2+1].val;
}
void addTag(LL k,LL val, LL op) {
    if (op == 1){
        node[k].val = (node[k].val * val) % m;
        node[k].add = (node[k].add * val) % m;
        node[k].multi = (node[k].multi * val) % m;
    } else {
        node[k].val = (node[k].val + val*(node[k].right - node[k].left+1)) % m;
        node[k].add = (node[k].add + val) % m;
    }
}
void pushDown(LL k){
    addTag(k*2 ,node[k].multi, 1);
    addTag(k*2, node[k].add, 2);
    addTag(k*2+1, node[k].multi, 1);
    addTag(k*2+1, node[k].add, 2);
    node[k].multi = 1; node[k].add = 0;

}
void modify(LL k, LL l, LL r, LL val ,LL op) {
    if (l <= node[k].left && node[k].right <= r) {
        addTag(k, val, op);
        return;
    }
    pushDown(k);
    LL mid = node[k].left + (node[k].right - node[k].left)/2;
    if (l <= mid) modify(k*2, l, r, val, op);
    if (r > mid) modify(k*2+1, l, r, val, op);
    node[k].val = node[k*2].val + node[k*2+1].val;
}
LL query(LL k, LL l, LL r) {
    if (l <= node[k].left && node[k].right <= r) {
        return node[k].val;
    }
    pushDown(k);
    LL mid = node[k].left + (node[k].right - node[k].left)/2, res = 0;
    if (l <= mid) res = (res + query(k*2, l, r)) % m;
    if (r >  mid) res = (res + query(k*2+1, l, r)) % m;
    return res;
}
int main() {
    scanf("%lld%lld%lld", &n, &q, &m);
    for(LL i=1; i<=n; ++i) {
        cin >> arr[i];
    }
    buildTree(root, 1, n);
    for(LL i=1;i<=q;++i){
        LL op, a, b, c;
        scanf("%lld", &op);
        if (op == 1 || op == 2) {
            scanf("%lld%lld%lld", &a, &b, &c);
            modify(root, a, b, c%m, op);
        } else {
            scanf("%lld%lld", &a, &b);
            printf("%lld\n",query(root, a, b));
        }
    }
    return 0;
}

注意事项

书写线段树的时候需要注意以下事项：

  • buildTree和modify函数在递归完成后的回溯阶段需要更新上层的统计值
  • 下放lazyTag所涉及的函数pushDown在query和modify中都是先调用再进行递归
  • 加lazyTag标记以及区间更新函数addTag都是对当前区间进行操作（标记是加给儿子节点看的,方便后续pushDown下去对儿子区间进行更新）

总结

线段树是一种强大的数据结构，特别适合于解决区间查询和更新问题。理解线段树的构建和操作原理，并掌握其实现方法，可以帮助我们高效地解决许多复杂的数据处理问题。

本站由 @anonymity 使用 Stellar 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。