区间修改主席树有两种写法，标记永久化和动态扩展。

注意事项：

  1. 标记永久化版使用上有一定局限性，只有在各种懒标记之间不冲突的情况下才能使用（如加法标记和乘法标记会相冲突，不能使用标记永久化主席树）；而动态扩展版没有这种限制。

  2. 记主席树开在长度为 nn 的区间上，操作数为 mm，layn=⌈log⁡n⌉+1\text{lay}n=\lceil\log n\rceil+1，标记永久化版的最大空间占用量（若初始版本为空）为 4mlayn4m\text{lay}n；动态扩展版的最大空间占用量（若初始版本为空）为 5mlayn5m\text{lay}n（不确定，不知道为什么）。

  3. 动态扩展版的函数 modify 中操作 pushdown 要提到最前面，并改为对节点 verid 进行 pushdown，这是为了避免提前创建节点 id 的儿子。

  4. 函数 build 和 modify 等有两种写法，「传入 id」和「不传入 id，返回 id」，建议使用后一种。

标记永久化版

Luogu U220120 【模板】区间修改主席树1

代码（该代码不带取模，不能 AC）：

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 1e5;
const int MAXnlay = 18;
const int MAXm = 1e5;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

const int MAXnd = MAXn * 4 + MAXnlay * MAXm * 4;
int cntroot, root[MAXm + 10];
int cntnd, ls[MAXnd + 10], rs[MAXnd + 10];
int sum[MAXnd + 10];
int lzadd[MAXnd + 10];
inline void clone(int id, int verid) {
    ls[id] = ls[verid];
    rs[id] = rs[verid];
    sum[id] = sum[verid];
    lzadd[id] = lzadd[verid];
}
inline void putadd(int id, int v, int len) {
    sum[id] += v * len;
    lzadd[id] += v;
}
inline void passadd(int id, int v, int len) {
    sum[id] += v * len;
}
int build(int *suma, int le, int ri) {
    int id = ++cntnd;
    sum[id] = suma[ri] - suma[le - 1];
    if (le == ri) {
        ;
    } else {
        int mid = (le + ri) >> 1;
        ls[id] = build(suma, le, mid);
        rs[id] = build(suma, mid + 1, ri);
    }
    return id;
}
int modify(int verid, int l, int r, int v, int le, int ri) {
    int id = ++cntnd;
    clone(id, verid);
    if (le >= l && ri <= r) {
        putadd(id, v, ri - le + 1);
    } else {
        passadd(id, v, min(r, ri) - max(l, le) + 1);
        int mid = (le + ri) >> 1;
        if (l <= mid) ls[id] = modify(ls[verid], l, r, v, le, mid);
        if (r > mid) rs[id] = modify(rs[verid], l, r, v, mid + 1, ri);
    }
    return id;
}
int query(int id, int l, int r, int le, int ri) {
    if (id == 0) return 0;
    if (le >= l && ri <= r) {
        return sum[id];
    } else {
        int mid = (le + ri) >> 1, ans = lzadd[id] * (min(r, ri) - max(l, le) + 1);
        if (l <= mid) ans += query(ls[id], l, r, le, mid);
        if (r > mid) ans += query(rs[id], l, r, mid + 1, ri);
        return ans;
    }
}

int t, n, m;
int a[MAXn + 10];
signed main() {
    read(t, n, m);
    if (t == 1) {
        for (int i = 1; i <= n; ++i){
            read(a[i]);
            a[i] = a[i] + a[i - 1];
        }
        root[0] = build(a, 1, n);
    }
    for (int i = 1, opt, ver, l, r, v; i <= m; ++i) {
        read(opt, ver, l, r);
        if (opt == 1) {
            read(v);
            root[++cntroot] = modify(root[ver], l, r, v, 1, n);
        } else {
            printf("%lld\n", query(root[ver], l, r, 1, n));
        }
    }
    return 0;
}

动态扩展版

Luogu U220120 【模板】区间修改主席树1

代码（该代码不带取模，不能 AC）：

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 1e5;
const int MAXlayn = 18;
const int MAXm = 1e5;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

const int MAXnd = MAXn * 4 + MAXm * MAXlayn * 5;
int cntroot, root[MAXn + 10];
int cntnd, ls[MAXnd + 10], rs[MAXnd + 10], inroot[MAXnd + 10];
int sum[MAXnd + 10];
int lzadd[MAXnd + 10];
inline void clone(int id, int verid) {
    ls[id] = ls[verid];
    rs[id] = rs[verid];
    inroot[id] = inroot[verid];
    sum[id] = sum[verid];
    lzadd[id] = lzadd[verid];
}
inline void putadd(int id, int len, int v) {
    sum[id] += v * len;
    lzadd[id] += v;
}
inline void pushdown(int id, int len) {
    if (len == 1) return;
    if (lzadd[id]) {
        if (inroot[ls[id]] != inroot[id]) {
            int oldson = ls[id];
            clone(ls[id] = ++cntnd, oldson); inroot[ls[id]] = inroot[id];
        }
        if (inroot[rs[id]] != inroot[id]) {
            int oldson = rs[id];
            clone(rs[id] = ++cntnd, oldson); inroot[rs[id]] = inroot[id];
        }
        putadd(ls[id], (len >> 1) + (len & 1), lzadd[id]);
        putadd(rs[id], len >> 1, lzadd[id]);
        lzadd[id] = 0;
    }
}
inline void pushup(int id) {
    sum[id] = sum[ls[id]] + sum[rs[id]];
}
int build(int inrt, int *a, int le, int ri) {	
    int id = ++cntnd;
    inroot[id] = inrt;
    if (le == ri) {
        sum[id] = a[le];
    } else {
        int mid = (le + ri) >> 1;
        ls[id] = build(inrt, a, le, mid);
        rs[id] = build(inrt, a, mid + 1, ri);
        pushup(id);
    }
    return id;
}
int modify(int verid, int inrt, int l, int r, int v, int le, int ri) {
    pushdown(verid, ri - le + 1);
    int id = ++cntnd;
    clone(id, verid); inroot[id] = inrt;
    if (le >= l && ri <= r) {
        putadd(id, ri - le + 1, v);
    } else {
        int mid = (le + ri) >> 1;
        if (l <= mid) ls[id] = modify(ls[verid], inrt, l, r, v, le, mid);
        if (r > mid) rs[id] = modify(rs[verid], inrt, l, r, v, mid + 1, ri);
        pushup(id);
    }
    return id;
}
int query(int id, int l, int r, int le, int ri) {
    if (id == 0) return 0;
    if (le >= l && ri <= r) {
        return sum[id];
    } else {
        pushdown(id, ri - le + 1);
        int mid = (le + ri) >> 1, ans = 0;
        if (l <= mid) ans += query(ls[id], l, r, le, mid);
        if (r > mid) ans += query(rs[id], l, r, mid + 1, ri);
        return ans;
    }
}

int t, n, m;
int a[MAXn + 10];

signed main() {
    read(t, n, m);
    ++cntroot;
    if (t == 1) {
        for (int i = 1; i <= n; ++i) {
            read(a[i]);
        }
        root[cntroot] = build(cntroot, a, 1, n);
    }
    for (int i = 1, opt, ver, l, r, v; i <= m; ++i) {
        read(opt, ver, l, r); ++ver;
        if (opt == 1) {
            read(v);
            ++cntroot;
            root[cntroot] = modify(root[ver], cntroot, l, r, v, 1, n);
        } else {
            printf("%lld\n", query(root[ver], l, r, 1, n));
        }
    }
    return 0;
}

Luogu U220145 【模板】区间修改主席树2

代码（该代码不带取模，不能 AC）：

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 1e5;
const int MAXlayn = 18;
const int MAXm = 1e5;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

const int MAXnd = MAXn * 4 + MAXm * MAXlayn * 5;
int cntroot, root[MAXn + 10];
int cntnd, ls[MAXnd + 10], rs[MAXnd + 10], inroot[MAXnd + 10];
int sum[MAXnd + 10];
int lzmul[MAXnd + 10], lzadd[MAXnd + 10];
inline void clone(int id, int verid) {
    ls[id] = ls[verid];
    rs[id] = rs[verid];
    inroot[id] = inroot[verid];
    sum[id] = sum[verid];
    lzadd[id] = lzadd[verid];
    lzmul[id] = lzmul[verid];
}
inline void putmul(int id, int v) {
    sum[id] = sum[id] * v;
    lzadd[id] = lzadd[id] * v;
    lzmul[id] = lzmul[id] * v;
}
inline void putadd(int id, int len, int v) {
    sum[id] += v * len;
    lzadd[id] += v;
}
inline void pushdown(int id, int len) {
    if (len == 1) return;
    if (lzadd[id] != 0 || lzmul[id] != 1) {
        if (inroot[ls[id]] != inroot[id]) {
            int oldson = ls[id];
            clone(ls[id] = ++cntnd, oldson); inroot[ls[id]] = inroot[id];
        }
        if (inroot[rs[id]] != inroot[id]) {
            int oldson = rs[id];
            clone(rs[id] = ++cntnd, oldson); inroot[rs[id]] = inroot[id];
        }
        if (lzmul[id] != 1) {
            putmul(ls[id], lzmul[id]);
            putmul(rs[id], lzmul[id]);
            lzmul[id] = 1;
        }
        if (lzadd[id] != 0) {
            putadd(ls[id], (len >> 1) + (len & 1), lzadd[id]);
            putadd(rs[id], len >> 1, lzadd[id]);
            lzadd[id] = 0;
        }
    }
}
inline void pushup(int id) {
    sum[id] = sum[ls[id]] + sum[rs[id]];
}
void init() {
    fill(begin(lzmul), end(lzmul), 1);
}
int build(int inrt, int *a, int le, int ri) {	
    int id = ++cntnd;
    inroot[id] = inrt;
    if (le == ri) {
        sum[id] = a[le];
    } else {
        int mid = (le + ri) >> 1;
        ls[id] = build(inrt, a, le, mid);
        rs[id] = build(inrt, a, mid + 1, ri);
        pushup(id);
    }
    return id;
}
int modifyadd(int verid, int inrt, int l, int r, int v, int le, int ri) {
    pushdown(verid, ri - le + 1);
    int id = ++cntnd;
    clone(id, verid); inroot[id] = inrt;
    if (le >= l && ri <= r) {
        putadd(id, ri - le + 1, v);
    } else {
        int mid = (le + ri) >> 1;
        if (l <= mid) ls[id] = modifyadd(ls[verid], inrt, l, r, v, le, mid);
        if (r > mid) rs[id] = modifyadd(rs[verid], inrt, l, r, v, mid + 1, ri);
        pushup(id);
    }
    return id;
}
int modifymul(int verid, int inrt, int l, int r, int v, int le, int ri) {
    pushdown(verid, ri - le + 1);
    int id = ++cntnd;
    clone(id, verid); inroot[id] = inrt;
    if (le >= l && ri <= r) {
        putmul(id, v);
    } else {
        int mid = (le + ri) >> 1;
        if (l <= mid) ls[id] = modifymul(ls[verid], inrt, l, r, v, le, mid);
        if (r > mid) rs[id] = modifymul(rs[verid], inrt, l, r, v, mid + 1, ri);
        pushup(id);
    }
    return id;
}
int query(int id, int l, int r, int le, int ri) {
    if (id == 0) return 0;
    if (le >= l && ri <= r) {
        return sum[id];
    } else {
        pushdown(id, ri - le + 1);
        int mid = (le + ri) >> 1, ans = 0;
        if (l <= mid) ans += query(ls[id], l, r, le, mid);
        if (r > mid) ans += query(rs[id], l, r, mid + 1, ri);
        return ans;
    }
}

int t, n, m;
int a[MAXn + 10];

signed main() {
    init();
    read(t, n, m);
    ++cntroot;
    if (t == 1) {
        for (int i = 1; i <= n; ++i) {
            read(a[i]);
        }
        root[cntroot] = build(cntroot, a, 1, n);
    }
    for (int i = 1, opt, ver, l, r, v; i <= m; ++i) {
        read(opt, ver, l, r); ++ver;
        if (opt == 1) {
            read(v);
            ++cntroot;
            root[cntroot] = modifyadd(root[ver], cntroot, l, r, v, 1, n);
        } else if (opt == 2) {
            read(v);
            ++cntroot;
            root[cntroot] = modifymul(root[ver], cntroot, l, r, v, 1, n);
        } else {
            printf("%lld\n", query(root[ver], l, r, 1, n));
        }
    }
    return 0;
}