线段树与懒标记#

线段树适合处理区间问题，比如：

区间求和
区间最大值
单点修改
区间修改

当题目既有区间查询，又有区间修改时，通常需要懒标记。

1、线段树解决什么问题#

假设有数组：

1
1 2 3 4 5

需要频繁执行：

1
查询 [l, r] 的和
2
把 [l, r] 中每个数都加上 c

如果每次都暴力遍历区间，复杂度太高。线段树可以把这些操作做到 O(log n)。

2、线段树节点存什么#

常见节点结构：

1
struct Node {
2
    int l, r;
3
    long long sum;
4
    long long add;
5
} tr[N * 4];

含义：

1
l, r：当前节点表示的区间
2
sum：当前区间的和
3
add：懒标记，表示这个区间整体还欠着多少增量没有下传

3、建树#

建树就是递归划分区间。

1
void build(int u, int l, int r) {
2
    tr[u] = {l, r, a[l], 0};
3

4
    if (l == r) return;
5

6
    int mid = (l + r) >> 1;
7
    build(u << 1, l, mid);
8
    build(u << 1 | 1, mid + 1, r);
9
    pushup(u);
10
}

u 是当前节点编号，左儿子是 u << 1，右儿子是 u << 1 | 1。

4、pushup：用子节点更新父节点#

1
void pushup(int u) {
2
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
3
}

父节点的区间和等于左右子区间的和。

5、懒标记是什么#

如果某次修改完全覆盖当前区间，就不需要继续递归到叶子节点。

比如要让 [1, 100] 都加 5，当前节点刚好表示 [1, 100]，直接更新：

1
sum += 区间长度 * 5
2
add += 5

这个 add 表示：以后如果需要访问子节点，再把这个修改传下去。

6、pushdown：下传懒标记#

1
void pushdown(int u) {
2
    auto& root = tr[u];
3
    auto& left = tr[u << 1];
4
    auto& right = tr[u << 1 | 1];
5

6
    if (root.add) {
7
        left.add += root.add;
8
        left.sum += (long long)(left.r - left.l + 1) * root.add;
9

10
        right.add += root.add;
11
        right.sum += (long long)(right.r - right.l + 1) * root.add;
12

13
        root.add = 0;
14
    }
15
}

只有当要继续往下访问子节点时，才需要 pushdown。

7、完整模板：区间加，区间求和#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
const int N = 100010;
5

6
int n, m;
7
long long a[N];
8

9
struct Node {
10
    int l, r;
11
    long long sum;
12
    long long add;
13
} tr[N * 4];
14

15
void pushup(int u) {
16
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
17
}
18

19
void build(int u, int l, int r) {
20
    tr[u] = {l, r, a[l], 0};
21

22
    if (l == r) return;
23

24
    int mid = (l + r) >> 1;
25
    build(u << 1, l, mid);
26
    build(u << 1 | 1, mid + 1, r);
27
    pushup(u);
28
}
29

30
void pushdown(int u) {
31
    auto& root = tr[u];
32
    auto& left = tr[u << 1];
33
    auto& right = tr[u << 1 | 1];
34

35
    if (root.add) {
36
        left.add += root.add;
37
        left.sum += (long long)(left.r - left.l + 1) * root.add;
38

39
        right.add += root.add;
40
        right.sum += (long long)(right.r - right.l + 1) * root.add;
41

42
        root.add = 0;
43
    }
44
}
45

46
void modify(int u, int l, int r, int d) {
47
    if (tr[u].l >= l && tr[u].r <= r) {
48
        tr[u].sum += (long long)(tr[u].r - tr[u].l + 1) * d;
49
        tr[u].add += d;
50
        return;
51
    }
52

53
    pushdown(u);
54

55
    int mid = (tr[u].l + tr[u].r) >> 1;
56
    if (l <= mid) modify(u << 1, l, r, d);
57
    if (r > mid) modify(u << 1 | 1, l, r, d);
58

59
    pushup(u);
60
}
61

62
long long query(int u, int l, int r) {
63
    if (tr[u].l >= l && tr[u].r <= r) {
64
        return tr[u].sum;
65
    }
66

67
    pushdown(u);
68

69
    int mid = (tr[u].l + tr[u].r) >> 1;
70
    long long res = 0;
71

72
    if (l <= mid) res += query(u << 1, l, r);
73
    if (r > mid) res += query(u << 1 | 1, l, r);
74

75
    return res;
76
}
77

78
int main() {
79
    cin >> n >> m;
80
    for (int i = 1; i <= n; i++) cin >> a[i];
81

82
    build(1, 1, n);
83

84
    while (m--) {
85
        char op;
86
        int l, r, d;
87
        cin >> op >> l >> r;
88

89
        if (op == 'Q') {
90
            cout << query(1, l, r) << endl;
91
        } else {
92
            cin >> d;
93
            modify(1, l, r, d);
94
        }
95
    }
96

97
    return 0;
98
}

8、容易写错的地方#

（1）数组要开 `4 * N`#

线段树节点数量一般开：

1
tr[N * 4]

不要只开 N。

（2）区间和建议用 `long long`#

区间加和区间求和很容易超过 int。

（3）查询和修改前要下传懒标记#

只要要访问子节点，就先：

1
pushdown(u);

否则子节点保存的值可能不是最新的。

原图笔记#

懒标记处理#

总结图#

总结#

线段树可以记成：

1
build 建树
2
pushup 子节点更新父节点
3
pushdown 懒标记下传
4
modify 区间修改
5
query 区间查询

懒标记的意义是：能不往下走就先不往下走，把修改暂存在当前节点，等真正需要访问子节点时再下传。

音乐

音乐

线段树与懒标记#

1、线段树解决什么问题#

2、线段树节点存什么#

3、建树#

4、pushup：用子节点更新父节点#

5、懒标记是什么#

6、pushdown：下传懒标记#

7、完整模板：区间加，区间求和#

8、容易写错的地方#

（1）数组要开 `4 * N`#

（2）区间和建议用 `long long`#

（3）查询和修改前要下传懒标记#

原图笔记#

懒标记处理#

总结图#

总结#

文章分享

音乐

文章目录

音乐

音乐

线段树与懒标记

线段树与懒标记#

1、线段树解决什么问题#

2、线段树节点存什么#

3、建树#

4、pushup：用子节点更新父节点#

5、懒标记是什么#

6、pushdown：下传懒标记#

7、完整模板：区间加，区间求和#

8、容易写错的地方#

（1）数组要开 4 * N#

（2）区间和建议用 long long#

（3）查询和修改前要下传懒标记#

原图笔记#

懒标记处理#

总结图#

总结#

文章分享

音乐

文章目录

（1）数组要开 `4 * N`#

（2）区间和建议用 `long long`#