给 \(n\) 个数 \(a_1, a_2, \cdots, a_n\) 。
支持 \(q\) 个操作：
- 1 l r d ，令所有的 \(a_i(l \leq i \leq r)\) 加上 \(d\) 。
- 2 l r ，查询 \(max_{i = l}^{r} a_i\) 。
区间修改的线段树要比基础线段树多考虑一个元素： \(lazy\ tag\) 。复杂的信息可以用多个标记表示。
\(lazy\ tag\) 称为“懒标记”或“延迟标记”，具体是因为只在往下递归前（query 或 modify）才把当前区间的标记下压，通常称为 \(pushdown\) 操作。标记下压打到左右儿子上，即打标记，通常称为 \(settag\) 操作。
-
\(pushdown\) 的步骤
- 存在标记时执行。只是一个习惯：一是常数优化，二是特殊情况下能避免错误
- 将当前的标记打到左右儿子。
- 清空/初始化当前的标记。
-
\(settag\) 的步骤
- 当前标记加上新标记。
- 当前信息加上新标记。
一：确定所需维护的信息，确定修改信息时需要的标记。确定信息与标记间的合并。封装 \(update\) 。封装 \(settag\) 和 \(pushdonw\) 。
- 所需维护的信息显然只有区间最大值 \(maxv\) ，修改信息的标记显然只是一个 \(add\) 。
struct Info {
ll maxv;
};
struct Tag {
ll add;
};
struct Node {
Info f;
Tag t;
} seg[N * 4];
Info operator + (const Info &l, const Info &r) {
Info ret;
if ( l.maxv > r.maxv ) ret = l;
else if ( r.maxv > l.maxv ) ret = r;
else ret = {l.maxv};
return ret;
}
Info operator + (const Info &f, const Tag &t) {
Info ret;
ret.maxv = f.maxv + t.add;
return ret;
}
Tag operator + (const Tag &t1, const Tag &t2) {
Tag ret;
ret.add = t1.add + t2.add;
return ret;
}
void update(int id) {
seg[id].f = seg[ id * 2 ].f + seg[ id * 2 + 1].f;
}
void settag(int id, tag t) {
seg[id].f = seg[id].f + t;
seg[id].t = seg[id].t + t;
}
void pushdown(int id) {
if (seg[id].t.add != 0) {
settag( id * 2, seg[id].t );
settag( id * 2 + 1, seg[id].t );
seg[id].t = {0};
}
}
二：写出主程序框架
int main() {
int n, q;
std::cin >> n >> q;
for (int i = 1; i <= n; i++) std::cin >> a[i];
build(1, 1, n);
for (int i = 1; i <= q; i++) {
int typ; std::cin >> typ;
if ( typ == 1 ) {
int l, r, d; std::cin >> l >> r >> d;
modify(1, 1, n, l, r, d);
}
else {
int l, r; std::cin >> l >> r;
auto ans = query(1, 1, n, l, r);
std::cout << "! " << ans.maxv << '\n';
}
}
return 0;
}
三：完成建树、查询、区间修改(打标记的线段树相比普通线段树，只在 query 的递归前多了一个 pushdown ，build 到叶子时多初始化一个 tag )。
\(build\) 需要初始化 \(Tag\) ，但是所有区间的 \(Tag\) 都要初始化，而不是和 \(Info\) 一样在叶子上初始化。
void build(int id, int l, int r) {
seg[id].t = {0};
if (l == r) {
seg[id].f = {a[l]};
}
else {
int mid = ( l + r ) >> 1;
build( id * 2, l, mid );
build( id * 2 + 1, mid + 1, r );
update(id);
}
}
\(query\) 在往下递归前需要压下标记。
Info query(int id, int l, int r, int ql, int qr) {
if (l == ql && r == qr) {
return seg[id].f;
}
else {
pushdown(id);
int mid = ( l + r ) >> 1;
if ( qr <= mid ) return query( id * 2, l, mid, ql, qr );
else if ( ql > mid ) return query( id * 2 + 1, mid + 1, r, ql, qr );
else return query( id * 2, l, mid, ql, mid ) + query( id * 2 + 1, mid + 1, r, mid + 1, qr);
}
}
注意理解区间修改：并不是值的修改，而是一个路径沿途压下标记、终点打上打标记的过程。相当于标记修改。
注意到modify 走到线段上会打标记，于是有两个点：
- 下层信息会更新，于是往下递归后需要当前信息要 \(update\) 。
- 树上一条路径的信息，下层更新之前要保证上层信息正确。所以往下递归前要 \(pushdown\) ，这可以确保 \(settag\) 时的信息就是当前路径上的真实信息。
- 线段树延迟标记的原理即 \(modify\) 和 \(query\) 的路径信息都是真实的，而不在乎其他路径。
- 显然与普通线段树的区别只在于 \(lazy\ tag\) 的构建、\(modify\) 函数、\(query\) 递归时的顺路压标记。即写法上几乎没有区别。
- 线段树延迟标记的原理即 \(modify\) 和 \(query\) 的路径信息都是真实的，而不在乎其他路径。
void modify(int id, int l, int r, int ql, int qr, Tag t) {
if (l == ql && r == qr) {
settag( id, t );
}
else {
pushdown(id);
int mid = ( l + r ) >> 1;
if ( qr <= mid ) modify( id * 2, l, mid, ql, qr, t );
else if ( ql > mid) modify( id * 2 + 1, mid + 1, r, ql, qr, t );
else modify( id * 2, l, mid, ql, mid, t ), modify( id * 2 + 1, mid + 1, r, mid + 1, qr, t );
update(id);
}
}
不难发现
- 单点修改线段树与打标记线段树几乎没有差距。存在 \(change\) 和 \(modify\) 函数的不同、\(query\) 递归前需要 \(pushdown\) 。
- 线段树只需要一个框架，关键是确定需要的信息、标记、其间合并方式。
完整代码
view
#include <bits/stdc++.h>
typedef long long ll;
const int N = 200005;
int a[N];
struct Info {
ll maxv;
};
struct Tag {
ll add;
};
struct Node {
Info f;
Tag t;
} seg[N * 4];
Info operator + (const Info &l, const Info &r) {
Info ret;
if ( l.maxv > r.maxv ) ret = l;
else if ( r.maxv > l.maxv ) ret = r;
else ret = {l.maxv};
return ret;
}
Info operator + (const Info &f, const Tag &t) {
Info ret;
ret.maxv = f.maxv + t.add;
return ret;
}
Tag operator + (const Tag &t1, const Tag &t2) {
Tag ret;
ret.add = t1.add + t2.add;
return ret;
}
void update(int id) {
seg[id].f = seg[ id * 2 ].f + seg[ id * 2 + 1].f;
}
void settag(int id, Tag t) {
seg[id].f = seg[id].f + t;
seg[id].t = seg[id].t + t;
}
void pushdown(int id) {
if (seg[id].t.add != 0) { // 一个习惯
settag( id * 2, seg[id].t );
settag( id * 2 + 1, seg[id].t );
seg[id].t = {0};
}
}
void build(int id, int l, int r) {
seg[id].t = {0};
if (l == r) {
seg[id].f = {a[l]};
}
else {
int mid = ( l + r ) >> 1;
build( id * 2, l, mid );
build( id * 2 + 1, mid + 1, r );
update(id);
}
}
Info query(int id, int l, int r, int ql, int qr) {
if (l == ql && r == qr) {
return seg[id].f;
}
else {
pushdown(id);
int mid = ( l + r ) >> 1;
if ( qr <= mid ) return query( id * 2, l, mid, ql, qr );
else if ( ql > mid ) return query( id * 2 + 1, mid + 1, r, ql, qr );
else return query( id * 2, l, mid, ql, mid ) + query( id * 2 + 1, mid + 1, r, mid + 1, qr);
}
}
void modify(int id, int l, int r, int ql, int qr, Tag t) {
if (l == ql && r == qr) {
settag( id, t );
}
else {
pushdown(id);
int mid = ( l + r ) >> 1;
if ( qr <= mid ) modify( id * 2, l, mid, ql, qr, t );
else if ( ql > mid) modify( id * 2 + 1, mid + 1, r, ql, qr, t );
else modify( id * 2, l, mid, ql, mid, t ), modify( id * 2 + 1, mid + 1, r, mid + 1, qr, t );
update(id);
}
}
int main() {
int n, q;
std::cin >> n >> q;
for (int i = 1; i <= n; i++) std::cin >> a[i];
build(1, 1, n);
for (int i = 1; i <= q; i++) {
int typ; std::cin >> typ;
if ( typ == 1 ) {
int l, r, d; std::cin >> l >> r >> d;
modify(1, 1, n, l, r, {d});
}
else {
int l, r; std::cin >> l >> r;
auto ans = query(1, 1, n, l, r);
std::cout << ans.maxv << '\n';
}
}
return 0;
}