0.前置知识

1.什么是线段树

线段树，是一种 二叉搜索树 。它将一段区间划分为若干 单位区间，每一个节点都储存着一个区间。它功能强大，支持区间求和，区间最大值，区间修改，单点修改等操作。

线段树的每个节点都存储的一段区间 $[l,r]$，如果是叶子节点，则 $l=r$。

它的大致思想是：将一段大区间平均地划分成 $2$ 个小区间，每一个小区间都再平均分成 $2$ 个更小区间，直到一个区间的 $l=r$ 才停止。

2. 它能干什么

像上文所说，它能支持区间求和，区间最大值的查询等，换句话说，它能支持的操作能使得区间 $[l,r]$ 可以由 $[l,mid]$ 和 $[mid+1,r]$ 的答案合并得到。

如区间众数的查询这类问题就不满足该条件。

1.建树

通过它的思想可知，每次将一个区间 $[l,r]$ 分为两个小区间 $\bigg[l,\left \lfloor \frac{l+r}{2} \right \rfloor \bigg]$，$\bigg[\left \lfloor \frac{l+r}{2} \right \rfloor +1,r\bigg]$ 进行维护，直到 $l=r$。

如一颗 $[1,10]$ 的线段树的维护过程（图片来自百度百科）

存储方法通常是堆式储存法，节点 $k$ 的左儿子为 $2\times k$，右儿子为 $2\times k+1$，表示区间 $[l,r]$。

$\texttt{Ps}$：线段树要开 $4 \sim 8$ 倍空间。

下文代码均为区间求和与区间加操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct arr
{
    int l,r;
    int sum;// 维护区间和
}tree[400002];
void update(int k)
{
    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
    // 该区间的和等于子区间的和
}
void build(int k,int l,int r)
// k 表示节点数，l 和 r 表示当前的左右边界
{
    tree[k].l=l;tree[k].r=r;// 存储区间 [l,r]
    if(l==r) //如果是叶节点
    {
        tree[k].sum=a[l];// a 数组表示给定的初始数组
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);build(k*2+1,mid+1,r);// 递归左右儿子建树
    update(k);// 用左右儿子的值更新当前节点
}

2.区间修改

可以借助图片理解。

  1. 修改区间与当前区间的左右区间均有交集；

可以将修改区间也对半分，然后递归左右区间实现修改操作。

  1. 修改区间仅与当前区间的左区间有交集；

这时候不用管右区间，直接递归左区间实现修改操作。

  1. 修改区间仅与当前区间的右区间有交集；

同理，只递归右区间即可。

  1. 修改区间与当前区间重合；

当前区间的 $\text{sum}$ 加上 $(r-l+1)\times x$，其中 $x$ 为区间加的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void change(int k,int l,int r,int x)
// 搜到节点 k，修改的区间为 [l,r]，区间加 x
{
    if(tree[k].l==l&&tree[k].r==r)// 情况 4
    {
        tree[k].sum+=(r-l+1)*x;
        return;
    }
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) change(k*2,l,r,x);// 情况 2
        else if(l>mid) change(k*2+1,l,r,x);// 情况 3
            else change(k*2,l,mid,x),change(k*2+1,mid+1,r,x);// 情况 4
    update(k);// 别忘了更新当前区间
}

3.区间查询

与区间修改类似。

  1. 查询区间如果与当前区间重合，则直接返回当前区间的 $\text{sum}$ 值。
  2. 查询区间如果仅与当前区间的左区间有交集，则返回递归左区间的值。
  3. 查询区间如果仅与当前区间的右区间有交集，则返回递归右区间的值。
  4. 查询区间如果与当前区间的左右区间均有交集，则返回递归左右区间的值的和。
1
2
3
4
5
6
7
8
9
int query(int k,int l,int r)
// 搜到节点 k，查询的区间为 [l,r] 
{
    if(tree[k].l==l&&tree[k].r==r) return tree[k].sum;// 情况 1 
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) return query(k*2,l,r);// 情况 2 
    if(l>mid) return query(k*2+1,l,r);// 情况 3
    return query(k*2,l,mid)+query(k*2+1,mid+1,r);// 情况 4 
}

4.懒标记

如果只是这样暴力修改与查询，复杂度甚至比朴素暴力还要高。

可以引入懒标记，在每次修改时假装已经给儿子节点修改，在每次查询操作时再下放。

举个例子，在将区间 $[1,5]$ 加 $3$ 时，可以给区间 $[1,5]$ 的 $\text{lazy}$ 标记上先加 $3$，在查询 $[1,3]$ 的区间和时再给其区间和加上 $(3-1+1)\times 3$。

注意在修改时也应先下传懒标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void pushdown(int k)
// 下传 k 节点的懒标记
{
    if(!tree[k].lazy) return;// 如果没有懒标记则不用下传 
    if(tree[k].l==tree[k].r)// 如果是叶节点则不用下传 
    {
        tree[k].lazy=0;
        return;
    }
    tree[k*2].sum+=(tree[k*2].r-tree[k*2].l+1)*tree[k].lazy;
    tree[k*2+1].sum+=(tree[k*2+1].r-tree[k*2+1].l+1)*tree[k].lazy;
    // 左右节点的区间和加上该节点懒标记
    tree[k*2].lazy+=tree[k].lazy;
    tree[k*2+1].lazy+=tree[k].lazy;
    // 左右节点的懒标记加上该节点的懒标记 
    tree[k].lazy=0;
    // 该节点的懒标记清空 
}

5.习题

模板 $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
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct arr
{
    int l,r,sum,lazy;
}tree[400002];
int n,m;
int a[100002];
int x,l,r,k;
void pushdown(int k)
{
    if(tree[k].l==tree[k].r)
    {
        tree[k].lazy=0;
        return;
    }
    tree[k*2].sum+=(tree[k*2].r-tree[k*2].l+1)*tree[k].lazy;
    tree[k*2+1].sum+=(tree[k*2+1].r-tree[k*2+1].l+1)*tree[k].lazy;
    tree[k*2].lazy+=tree[k].lazy;
    tree[k*2+1].lazy+=tree[k].lazy;
    tree[k].lazy=0;
}
void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;
    if(l==r)
    {
        tree[k].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);build(k*2+1,mid+1,r);
    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
}
void change(int k,int l,int r,int x)
{
    if(tree[k].l==l&&tree[k].r==r)
    {
        tree[k].sum+=x*(r-l+1);
        tree[k].lazy+=x;
        return;
    }
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) change(k*2,l,r,x);
        else if(l>mid) change(k*2+1,l,r,x);
            else change(k*2,l,mid,x),change(k*2+1,mid+1,r,x);
    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
}
int query(int k,int l,int r)
{
    if(tree[k].lazy) pushdown(k);
    if(tree[k].l==l&&tree[k].r==r) return tree[k].sum;
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) return query(k*2,l,r);
    if(l>mid) return query(k*2+1,l,r);
    return query(k*2,l,mid)+query(k*2+1,mid+1,r);
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;++i)
    {
        cin>>x>>l>>r;
        if(x==1)
        {
            cin>>k;
            change(1,l,r,k);
        }
        else
        {
            cout<<query(1,l,r)<<"\n";
        }
    }
    return 0;
}

模板 $2$

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct arr
{
    int l,r,sum;
    int lazy1;// 乘法
    int lazy2;// 加法 
}tree[400002];
int n,m,mo;
int a[100002];
int x,l,r,k;
void pushdown(int k)
{
    tree[k*2].sum=((tree[k*2].r-tree[k*2].l+1)*tree[k].lazy2%mo+tree[k*2].sum*tree[k].lazy1%mo)%mo;
    tree[k*2+1].sum=((tree[k*2+1].r-tree[k*2+1].l+1)*tree[k].lazy2%mo+tree[k*2+1].sum*tree[k].lazy1%mo)%mo;
    tree[k*2].lazy1=(tree[k*2].lazy1*tree[k].lazy1)%mo;
    tree[k*2+1].lazy1=(tree[k*2+1].lazy1*tree[k].lazy1)%mo;
    tree[k*2].lazy2=(tree[k*2].lazy2*tree[k].lazy1%mo+tree[k].lazy2)%mo;
    tree[k*2+1].lazy2=(tree[k*2+1].lazy2*tree[k].lazy1%mo+tree[k].lazy2)%mo;
    tree[k].lazy1=1;tree[k].lazy2=0;
}
void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;tree[k].lazy1=1;
    if(l==r)
    {
        tree[k].sum=a[l]%mo;
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);build(k*2+1,mid+1,r);
    tree[k].sum=(tree[k*2].sum+tree[k*2+1].sum)%mo;
}
void change1(int k,int l,int r,int x)
{
    if(tree[k].l==l&&tree[k].r==r)
    {
        tree[k].sum=(tree[k].sum*x)%mo;
        tree[k].lazy1=(tree[k].lazy1*x)%mo;
        tree[k].lazy2=(tree[k].lazy2*x)%mo;
        return;
    }
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) change1(k*2,l,r,x);
        else if(l>mid) change1(k*2+1,l,r,x);
            else change1(k*2,l,mid,x),change1(k*2+1,mid+1,r,x);
    tree[k].sum=(tree[k*2].sum+tree[k*2+1].sum)%mo;
}
void change2(int k,int l,int r,int x)
{
    if(tree[k].l==l&&tree[k].r==r)
    {
        tree[k].sum=(tree[k].sum+x*(r-l+1)%mo)%mo;
        tree[k].lazy2=(tree[k].lazy2+x)%mo;
        return;
    }
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) change2(k*2,l,r,x);
        else if(l>mid) change2(k*2+1,l,r,x);
            else change2(k*2,l,mid,x),change2(k*2+1,mid+1,r,x);
    tree[k].sum=(tree[k*2].sum+tree[k*2+1].sum)%mo;
}
int query(int k,int l,int r)
{
    if(tree[k].l==l&&tree[k].r==r) return tree[k].sum;
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) return query(k*2,l,r)%mo;
    if(l>mid) return query(k*2+1,l,r)%mo;
    return (query(k*2,l,mid)+query(k*2+1,mid+1,r))%mo;
}
signed main()
{
    cin>>n>>m>>mo;
    for(int i=1;i<=n;++i) cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=m;++i)
    {
        cin>>x>>l>>r;
        if(x==1)
        {
            cin>>k;
            change1(1,l,r,k);
        }
        else if(x==2)
        {
            cin>>k;
            change2(1,l,r,k);
        }
        else
        {
            cout<<query(1,l,r)<<"\n";
        }
    }
    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
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
#include<bits/stdc++.h>
using namespace std;
struct arr
{
    int l,r;
    int lazy;// 取反操作
    int sum;// 区间中 1 的个数
    int to;// 改为 0 或 1，-1 表示没改
    int conl0;// 从 l 往 r 有多少续的 0
    int conr0;// 从 r 往 l 有多少续的 0
    int conl1;// 从 l 往 r 有多少续的 1
    int conr1;// 从 r 往 l 有多少续的 1
    int ma0;// 最长连续 0 的个数
    int ma1;// 最长连续 1 的个数
    int len;// 区间长度
}tree[400002];
int n,m;
int a[100002];
int op,x,y;
int MIN(int a,int b)
{
    if(a<b) return a;
    return b;
}
int MAX(int a,int b)
{
    if(a>b) return a;
    return b;
}
int Max(int a,int b,int c)
{
    return MAX(MAX(a,b),c);
}
void update(int k)
{
    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
    if(tree[k*2].ma0==tree[k*2].len) tree[k].conl0=tree[k*2].len+tree[k*2+1].conl0;
        else tree[k].conl0=tree[k*2].conl0;
    if(tree[k*2+1].ma0==tree[k*2+1].len) tree[k].conr0=tree[k*2+1].len+tree[k*2].conr0;
        else tree[k].conr0=tree[k*2+1].conr0;
    if(tree[k*2].ma1==tree[k*2].len) tree[k].conl1=tree[k*2].len+tree[k*2+1].conl1;
        else tree[k].conl1=tree[k*2].conl1;
    if(tree[k*2+1].ma1==tree[k*2+1].len) tree[k].conr1=tree[k*2+1].len+tree[k*2].conr1;
        else tree[k].conr1=tree[k*2+1].conr1;
    tree[k].ma0=Max(tree[k*2].ma0,tree[k*2+1].ma0,tree[k*2].conr0+tree[k*2+1].conl0);
    tree[k].ma1=Max(tree[k*2].ma1,tree[k*2+1].ma1,tree[k*2].conr1+tree[k*2+1].conl1);
}
void pushdown(int k)
{
    if(tree[k].to==0)
    {
        tree[k*2].ma0=tree[k*2].conl0=tree[k*2].conr0=tree[k*2].len;
        tree[k*2].sum=tree[k*2].ma1=tree[k*2].conl1=tree[k*2].conr1=0;
        tree[k*2+1].ma0=tree[k*2+1].conl0=tree[k*2+1].conr0=tree[k*2+1].len;
        tree[k*2+1].sum=tree[k*2+1].ma1=tree[k*2+1].conl1=tree[k*2+1].conr1=0;
        tree[k*2].to=0;tree[k*2].lazy=0;
        tree[k*2+1].to=0;tree[k*2+1].lazy=0;
        tree[k].to=-1;tree[k].lazy=0;
    }
    if(tree[k].to==1)
    {
        tree[k*2].ma0=tree[k*2].conl0=tree[k*2].conr0=0;
        tree[k*2].sum=tree[k*2].ma1=tree[k*2].conl1=tree[k*2].conr1=tree[k*2].len;
        tree[k*2+1].ma0=tree[k*2+1].conl0=tree[k*2+1].conr0=0;
        tree[k*2+1].sum=tree[k*2+1].ma1=tree[k*2+1].conl1=tree[k*2+1].conr1=tree[k*2+1].len;
        tree[k*2].to=1;tree[k*2].lazy=0;
        tree[k*2+1].to=1;tree[k*2+1].lazy=0;
        tree[k].to=-1;tree[k].lazy=0;
    }
    if(tree[k].lazy)
    {
        tree[k*2].sum=tree[k*2].len-tree[k*2].sum;
        tree[k*2+1].sum=tree[k*2+1].len-tree[k*2+1].sum;
        swap(tree[k*2].ma0,tree[k*2].ma1);
        swap(tree[k*2+1].ma0,tree[k*2+1].ma1);
        swap(tree[k*2].conl0,tree[k*2].conl1);
        swap(tree[k*2+1].conl0,tree[k*2+1].conl1);
        swap(tree[k*2].conr0,tree[k*2].conr1);
        swap(tree[k*2+1].conr0,tree[k*2+1].conr1);
        if(tree[k*2].to==0) tree[k*2].to=1;
            else if(tree[k*2].to==1) tree[k*2].to=0;
                else tree[k*2].lazy=1-tree[k*2].lazy;
        if(tree[k*2+1].to==0) tree[k*2+1].to=1;
            else if(tree[k*2+1].to==1) tree[k*2+1].to=0;
                else tree[k*2+1].lazy=1-tree[k*2+1].lazy;
        tree[k].lazy=0;
    }
}
void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;
    tree[k].lazy=0;
    tree[k].to=-1;
    tree[k].len=r-l+1;
    if(l==r)
    {
        tree[k].sum=a[l];
        if(a[l]==0) tree[k].conl0=tree[k].conr0=tree[k].ma0=1;
        if(a[l]==1) tree[k].conl1=tree[k].conr1=tree[k].ma1=1;
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);build(k*2+1,mid+1,r);
    update(k);
}
void change_to0(int k,int l,int r)
{
    pushdown(k);
    if(tree[k].l==l&&tree[k].r==r)
    {
        tree[k].ma0=tree[k].conl0=tree[k].conr0=tree[k].len;
        tree[k].ma1=tree[k].conl1=tree[k].conr1=0;
        tree[k].sum=0;
        tree[k].to=0;
        tree[k].lazy=0;
        return;
    }
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) change_to0(k*2,l,r);
        else if(l>mid) change_to0(k*2+1,l,r);
            else change_to0(k*2,l,mid),change_to0(k*2+1,mid+1,r);
    update(k);
}
void change_to1(int k,int l,int r)
{
    pushdown(k);
    if(tree[k].l==l&&tree[k].r==r)
    {
        tree[k].ma0=tree[k].conl0=tree[k].conr0=0;
        tree[k].ma1=tree[k].conl1=tree[k].conr1=tree[k].len;
        tree[k].sum=tree[k].len;
        tree[k].to=1;
        tree[k].lazy=0;
        return;
    }
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) change_to1(k*2,l,r);
        else if(l>mid) change_to1(k*2+1,l,r);
            else change_to1(k*2,l,mid),change_to1(k*2+1,mid+1,r);
    update(k);
}
void change_lazy(int k,int l,int r)
{
    pushdown(k);
    if(tree[k].l==l&&tree[k].r==r)
    {
        tree[k].sum=tree[k].len-tree[k].sum;
        swap(tree[k].ma0,tree[k].ma1);
        swap(tree[k].conl0,tree[k].conl1);
        swap(tree[k].conr0,tree[k].conr1);
        tree[k].lazy=1-tree[k].lazy;
        return;
    }
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) change_lazy(k*2,l,r);
        else if(l>mid) change_lazy(k*2+1,l,r);
            else change_lazy(k*2,l,mid),change_lazy(k*2+1,mid+1,r);
    update(k);
}
int query_sum(int k,int l,int r)
{
    pushdown(k);
    if(tree[k].l==l&&tree[k].r==r) return tree[k].sum;
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) return query_sum(k*2,l,r);
    if(l>mid) return query_sum(k*2+1,l,r);
    return query_sum(k*2,l,mid)+query_sum(k*2+1,mid+1,r);
}
int query_con(int k,int l,int r)
{
    pushdown(k);
    if(tree[k].l==l&&tree[k].r==r) return tree[k].ma1;
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) return query_con(k*2,l,r);
    if(l>mid) return query_con(k*2+1,l,r);
    return Max(query_con(k*2,l,mid),query_con(k*2+1,mid+1,r),MIN(tree[k*2+1].conl1,r-mid)+MIN(tree[k*2].conr1,mid-l+1));
}
void check()
{
    for(int i=1;i<=4*n;++i)
    {
        if(tree[i].l==0&&tree[i].r==0) break;
        cout<<tree[i].l<<" "<<tree[i].r<<" "<<tree[i].conl1<<" "<<tree[i].conr1<<"\n";
    }
    puts("");
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>a[i];
    build(1,1,n);
    for(int i=1;i<=4*n;++i) tree[i].to=-1;
    for(int i=1;i<=m;++i)
    {
        cin>>op>>x>>y;
        x++;y++;
        if(op==0) change_to0(1,x,y);
        if(op==1) change_to1(1,x,y);
        if(op==2) change_lazy(1,x,y);
        if(op==3) cout<<query_sum(1,x,y)<<"\n";
        if(op==4) cout<<query_con(1,x,y)<<"\n";
//        if(op==5) check();
    }
    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
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct arr
{
    int l,r,sum,ma;
}tree[1600002];
int n,m;
int a[100002];
int k,l,r;
int Max(int x,int y)
{
    if(x>y) return x;
    return y;
}
void update(int k)
{
    tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
    tree[k].ma=Max(tree[k*2].ma,tree[k*2+1].ma);
}
void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;
    if(l==r)
    {
        tree[k].sum=tree[k].ma=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);build(k*2+1,mid+1,r);
    update(k);
}
void change(int k,int l,int r)
{
    if(tree[k].l==tree[k].r)
    {
        tree[k].sum=sqrt(tree[k].sum);
        tree[k].ma=sqrt(tree[k].ma);
        return;
    }
    int mid=(tree[k].l+tree[k].r)/2;
    if(l<=mid&&tree[k*2].ma>1) change(k*2,l,r);
    if(r>mid&&tree[k*2+1].ma>1) change(k*2+1,l,r);
    update(k);
}
int query(int k,int l,int r)
{
    if(l==tree[k].l&&r==tree[k].r) return tree[k].sum;
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) return query(k*2,l,r);
    if(l>mid) return query(k*2+1,l,r);
    return query(k*2,l,mid)+query(k*2+1,mid+1,r);
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    build(1,1,n);
    cin>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>k>>l>>r;
        if(l>r) swap(l,r);
        if(k==0) change(1,l,r);
            else cout<<query(1,l,r)<<"\n";
    }
    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
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct arr
{
    int l,r,add,ma,cover;
}tree[8000002];
int n,q;
int a[1000002];
int op,l,r,x;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int Max(int x,int y)
{
    if(x>y) return x;
    return y;
}
void cover_down(int k)
{
    if(tree[k].cover==-1) return;
    tree[k*2].add=tree[k*2+1].add=0;
    tree[k*2].ma=tree[k*2+1].ma=tree[k].cover;
    tree[k*2].cover=tree[k*2+1].cover=tree[k].cover;
    tree[k].cover=-1;
}
void add_down(int k)
{
    if(!tree[k].add) return;
    cover_down(k);
    tree[k*2].ma+=tree[k].add;
    tree[k*2+1].ma+=tree[k].add;
    tree[k*2].add+=tree[k].add;
    tree[k*2+1].add+=tree[k].add;
    tree[k].add=0;
}
void pushdown(int k)
{
    cover_down(k);
    add_down(k);
}
void build(int k,int l,int r)
{
    tree[k].l=l;tree[k].r=r;
    if(l==r)
    {
        tree[k].ma=a[l];
        tree[k].add=0;
        tree[k].cover=-1;
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);build(k*2+1,mid+1,r);
    tree[k].ma=Max(tree[k*2].ma,tree[k*2+1].ma);
}
void change_cover(int k,int l,int r,int x)
{
    if(tree[k].l==l&&tree[k].r==r)
    {
        tree[k].add=0;
        tree[k].ma=x;
        tree[k].cover=x;
        return;
    }
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) change_cover(k*2,l,r,x);
        else if(l>mid) change_cover(k*2+1,l,r,x);
            else change_cover(k*2,l,mid,x),change_cover(k*2+1,mid+1,r,x);
    tree[k].ma=Max(tree[k*2].ma,tree[k*2+1].ma);
}
void change_add(int k,int l,int r,int x)
{
    if(tree[k].l==l&&tree[k].r==r)
    {
        cover_down(k);
        tree[k].add+=x;
        tree[k].ma+=x;
        return;
    }
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) change_add(k*2,l,r,x);
        else if(l>mid) change_add(k*2+1,l,r,x);
            else change_add(k*2,l,mid,x),change_add(k*2+1,mid+1,r,x);
    tree[k].ma=Max(tree[k*2].ma,tree[k*2+1].ma);
}
int query(int k,int l,int r)
{
    if(tree[k].l==l&&tree[k].r==r) return tree[k].ma;
    pushdown(k);
    int mid=(tree[k].l+tree[k].r)/2;
    if(r<=mid) return query(k*2,l,r);
    if(l>mid) return query(k*2+1,l,r);
    return Max(query(k*2,l,mid),query(k*2+1,mid+1,r));
}
signed main()
{
    n=read();q=read();
    for(int i=1;i<=n;++i) a[i]=read();
    build(1,1,n);
    for(int i=1;i<=n*4;++i) tree[i].cover=-1;
    for(int i=1;i<=q;++i)
    {
        op=read();l=read();r=read();
        if(op==1) change_cover(1,l,r,read());
        if(op==2) change_add(1,l,r,read());
        if(op==3) cout<<query(1,l,r)<<"\n";
    }
    return 0;
}

6.总结

学的太晚了（悲）。

参考资料：

https://blog.csdn.net/huangzihaoal/article/details/81813454