线段树那些事：从模板题入手（洛谷P3372、P3373：区间加、区间乘、区间和查询）

模板题目

luogu-P3372-线段树1
luogu-P3373-线段树2
两道题都是比较基础的模板题，线段树1只有区间加、区间和查询，线段树2增加了区间乘的操作。

关于线段树需要注意的

这篇文章不是讲题解的（洛谷大神们写的老清楚了，OI Wiki写的也很好），而是讲一些刚接触线段树（像我一样）在写的时候容易遇到的疑惑和细节问题。

一些疑惑

• 是否需要存储节点的左右端点：都可以。存储的好处是程序会变快，递归压栈的时候少两个参数的push/pop，缺点是空间占用以及程序在写的时候会相对繁琐一点。
• 叶子结点是否需要特判，被打上懒惰标记了怎么办：可以不特判，只要程序写的是正确的，叶子结点是不会被pushdown的。
• pushdown操作是否需要特判：可以不要，建议不要。特判很容易出错。
• 所有的递归函数是否需要加入“非法状态出口”：最初写区间修改、查询的递归函数时总认为可能会查询到不在查询目标的范围内，从而陷入死循环，其实这个问题在递归函数调用时已经解决，例如：

      if (l <= mid) update_add(curr<<1, l, r, k); // 根据左右端点和中点的位置关系进行分类
      if (r > mid) update_add(curr<<1|1, l, r, k);
  1
  2

  因此程序根本不会进入“非法状态”，即不需要额外特判出口。

细节问题

• 空间开辟的大小问题：比较通用的细节问题，比如题目明确数据范围在1e5以内，不要恰好开1e5，因为你在使用数组的时候可能为了方便不会从0开始（比如从1开始），这时候如果刚好数据给满了，就会覆盖全局数据区后面的变量的内容。我实实在在遇到过一次这个问题，debug了很久……
• 乘法的单位元是1：涉及乘法操作的懒惰标记，记得要初始化为单位元1，至于原因……

关于这两道模板题

其实难点就一个“先乘后加”，需要注意每一次的乘法因子对于其作用的区间和、加法标记和乘法标记都是乘的关系；由于先乘后加，加法懒惰标记已经涵盖了之前的所有乘法的内容，因此可以在pushdown的时候直接加入。pushdown唯一需要关注的就是先对下一层执行乘法，再执行加法，分开写可能会比较清晰（见代码）。

P3373代码

#include <iostream>
using namespace std;

const int n_MAX = 1e5+5;    // 没有+5导致数据给到100000的时候数组a溢出然后n被覆盖！
typedef long long ll;
struct node {
    ll l, r;
    ll mul;
    ll add;
    ll sum;
}tree[4*n_MAX];

ll a[n_MAX];
ll n, m, p;

void pushup(ll curr) {
    tree[curr].sum = (tree[curr<<1].sum + tree[(curr<<1)+1].sum) % p;
}

void build(ll curr, ll l, ll r) {
    tree[curr].l = l;
    tree[curr].r = r;
    tree[curr].sum = 0;
    tree[curr].mul = 1;         // 乘法的单位元是1
    if (l == r) {
        tree[curr].sum = a[l] % p;
        return;
    }
    ll mid = l + ((r - l) >> 1);
    build(curr<<1, l, mid);
    build(curr<<1|1, mid+1, r);
    pushup(curr);
    return;
}

void pushdown(ll curr) {    // 不要画蛇添足，不需要判断是否是叶子结点，不必增加add和mul是否有的条件
    ll leftlen = tree[curr<<1].r - tree[curr<<1].l + 1;
    ll rightlen = tree[(curr<<1)+1].r - tree[(curr<<1)+1].l + 1;

    tree[curr<<1].sum = (tree[curr<<1].sum * tree[curr].mul) % p;           // 先乘后加
    tree[(curr<<1)+1].sum = (tree[(curr<<1)+1].sum * tree[curr].mul) % p;
    tree[curr<<1].mul = (tree[curr<<1].mul * tree[curr].mul) % p;
    tree[(curr<<1)+1].mul = (tree[(curr<<1)+1].mul * tree[curr].mul) % p;
    tree[curr<<1].add = (tree[curr<<1].add * tree[curr].mul) % p;
    tree[(curr<<1)+1].add = (tree[(curr<<1)+1].add * tree[curr].mul) % p;

    tree[curr<<1].sum = (tree[curr<<1].sum + (leftlen * tree[curr].add) % p) % p;
    tree[curr<<1].add = (tree[curr<<1].add + tree[curr].add) % p;
    tree[(curr<<1)+1].sum = (tree[(curr<<1)+1].sum + (rightlen * tree[curr].add) % p) % p;
    tree[(curr<<1)+1].add = (tree[(curr<<1)+1].add + tree[curr].add) % p;

    tree[curr].add = 0;
    tree[curr].mul = 1;
}

void update_add(ll curr, ll l, ll r, ll k) {
    if (l <= tree[curr].l && r >= tree[curr].r) {
        tree[curr].sum = (tree[curr].sum + (tree[curr].r - tree[curr].l + 1) * k) % p;
        tree[curr].add = (tree[curr].add + k) % p;
        return;
    }
    ll mid = tree[curr].l + ((tree[curr].r - tree[curr].l) >> 1);
    pushdown(curr);
    if (l <= mid) update_add(curr<<1, l, r, k); // 根据左右端点和中点的位置关系进行分类
    if (r > mid) update_add(curr<<1|1, l, r, k);
    pushup(curr);
}

void update_mul(ll curr, ll l, ll r, ll k) {
    if (l <= tree[curr].l && r >= tree[curr].r) {
        tree[curr].sum = (tree[curr].sum * k) % p;
        tree[curr].add = (tree[curr].add * k) % p;
        tree[curr].mul = (tree[curr].mul * k) % p;          // debug: 乘法系数不是相加，是连乘
        return;
    }
    ll mid = tree[curr].l + ((tree[curr].r - tree[curr].l) >> 1);
    pushdown(curr);
    if (l <= mid) update_mul(curr<<1, l, r, k); // 根据左右端点和中点的位置关系进行分类
    if (r > mid) update_mul(curr<<1|1, l, r, k);
    pushup(curr);
}

ll query(ll curr, ll l, ll r) {
    if (l <= tree[curr].l && r >= tree[curr].r) return tree[curr].sum;

    ll mid = tree[curr].l + ((tree[curr].r - tree[curr].l) >> 1);
    pushdown(curr);
    ll sum = 0;
    if (l <= mid) sum = (sum + query(curr<<1, l, r)) % p;
    if (r > mid) sum = (sum + query(curr<<1|1, l, r)) % p;
    return sum;
}

int main() {
    scanf("%lld%lld%lld", &n, &m, &p);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    build(1, 1, n);

    while (m--) {
        ll type, x, y, k;
        scanf("%lld", &type);
        switch (type) {
            case 1:
                scanf("%lld%lld%lld", &x, &y, &k);
                update_mul(1, x, y, k);
                break;
            case 2:
                scanf("%lld%lld%lld", &x, &y, &k);
                update_add(1, x, y, k);
                break;
            case 3:
                scanf("%lld%lld", &x, &y);
                ll res = query(1, x, y);
                printf("%lld\n", res);
                break;
        }
    }
    return 0;
}
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121