一锅炖不下的博客
线段树
一锅炖不下
  2024-11-07 15:21:18   2024-11-10 21:47:47

线段树可以解决什么问题？对于[L, R]区间，它的答案可以由[L, M]和[M + 1, R]合并求出，具有这种性质的问题适合用线段树来解决。例如区间求和，大区间的和可以直接由两个子区间的和相加得到；还有区间最大/最小值问题，也可以比较两个子区间的最大/最小值，选出更大/更小的那一个作为结果。

不适合解决什么问题？区间众数，区间最长连续，最长不下降问题。除此之外，线段树似乎也不支持数据插入，因为插入会破坏平衡树的结构？

线段树主要有几个操作：

一、建树

以堆方式存储

二、单点修改/区间修改

区间修改后的查询要用到lazy标记，lazy标记是线段树的精髓所在，如果在区间修改的时候不采用lazy标记，而是搜索这个区间中的节点一一修改，那么与常规暴力遍历修改的时间复杂度其实拉不开差距。

lazy标记的具体使用过程如下，在区间修改时，如果修改的区间完全覆盖了某区间，那么就把这个区间打上lazy标记，这个区间囊括的子区间则暂时不更新，由后续查询遍历到子区间时检测到lazy标记做懒更新。

三、区间查询

四、与树状数组的异同

优点：

  • 线段树的区间修改的时间复杂度仍然是O(logn)，而树状数组的区间修改的时间复杂度是O(klogn)，k为区间元素个数
  • 线段树的应用范围更广，满足区间运算性质的问题都可以用线段树来求，例如区间最大/小值和区间和等等，而树状数组只能用来求区间和

缺点：

  • 线段树的实现较复杂
  • 线段树的空间复杂度较高

例题P3372 【模板】线段树 1

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
public class SegmentTree {
    // 原始数据数组
    private final long[] data;
    // 线段树，以堆方式表达
    private final Node[] tree;

    SegmentTree(long[] data) {
        this.data = data;
        tree = new Node[data.length * 4];
    }

    // 节点类，每个节点需要存储该节点管辖的左右边界，区间结果，以及lazy标记
    private static class Node {
        int l;
        int r;
        long sum;
        long lazy;
    }

    // 1. 后序递归建树，先建立子节点，再建立父节点
    public void build(int i, int l, int r) {
        // 实例化当前节点
        tree[i] = new Node();
        // 为当前节点的左右边界赋值
        tree[i].l = l;
        tree[i].r = r;
        // 终止条件，遍历到叶子节点，直接赋值
        if (l == r) {
            tree[i].sum = data[r];
            return;
        }
        int mid = l + (r - l) >> 1;
        build(i << 1, l, mid);
        // (i << 1) | 1 为位运算，等效为 2 * i + 1
        build((i << 1) | 1, mid + 1, r);
        tree[i].sum = tree[i << 1].sum + tree[(i << 1) | 1].sum;
    }

    // 2. 单点修改/区间修改
    public void update(int i, int l, int r, int k) {
        // 如果当前节点被[l, r]覆盖，当前节点更新，打上lazy标记
        if (tree[i].l >= l && tree[i].r <= r) {
            tree[i].sum += (long) k * (l - r + 1);
            tree[i].lazy += k;
            return;
        }
        // 如果未被覆盖，lazy下推
        if (tree[i].lazy != 0) {
            pushDown(i);
        }
        // 更新左子区间
        if (tree[i << 1].r >= l) {
            update(i << 1, l, r, k);
        }
        // 更新右子区间
        if (tree[(i << 1) | 1].l <= r) {
            update((i << 1) | 1, l, r, k);
        }
        // 更新当前节点
        tree[i].sum = tree[i << 1].sum + tree[(i << 1) | 1].sum;
    }

    // lazy下推操作
    public void pushDown(int i) {
        // 更新子区间lazy值
        long lazy = tree[i].lazy;
        tree[i << 1].lazy += lazy;
        tree[(i << 1) + 1].lazy += lazy;
        int mid = tree[i].l + (tree[i].r - tree[i].l) >> 1;
        // 更新子区间和
        tree[i << 1].sum += lazy * (mid - tree[i].l + 1);
        tree[(i << 1) + 1].sum += lazy * (tree[i].r - mid);
        tree[i].lazy = 0;
    }

    // 3. 区间查询
    public long query(int i, int l, int r) {
        // 覆盖则直接返回
        if (tree[i].r <= r && tree[i].l >= l) {
            return tree[i].sum;
        }
        if (tree[i].lazy != 0) {
            pushDown(i);
        }
        long temp = 0;
        if (tree[i << 1].r >= l) {
            temp += query(i << 1, l, r);
        }
        if (tree[(i << 1) | 1].l <= r) {
            temp += query((i << 1) | 1, l, r);
        }
        return temp;
    }
}