Daimayuan Online Judge 线段树打标记1

给 \(n\) 个数 \(a_1, a_2, \cdots, a_n\) 。
支持 \(q\) 个操作：

1. 1 l r d ，令所有的 \(a_i(l \leq i \leq r)\) 加上 \(d\) 。
2. 2 l r ，查询 \(max_{i = l}^{r} a_i\) 。

区间修改的线段树要比基础线段树多考虑一个元素： \(lazy\ tag\) 。复杂的信息可以用多个标记表示。

\(lazy\ tag\) 称为“懒标记”或“延迟标记”，具体是因为只在往下递归前（query 或 modify）才把当前区间的标记下压，通常称为 \(pushdown\) 操作。标记下压打到左右儿子上，即打标记，通常称为 \(settag\) 操作。

1. \(pushdown\) 的步骤

   1. 存在标记时执行。只是一个习惯：一是常数优化，二是特殊情况下能避免错误
   2. 将当前的标记打到左右儿子。
   3. 清空/初始化当前的标记。

2. \(settag\) 的步骤

   1. 当前标记加上新标记。
   2. 当前信息加上新标记。

一：确定所需维护的信息，确定修改信息时需要的标记。确定信息与标记间的合并。封装 \(update\) 。封装 \(settag\) 和 \(pushdonw\) 。

1. 所需维护的信息显然只有区间最大值 \(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 走到线段上会打标记，于是有两个点：

1. 下层信息会更新，于是往下递归后需要当前信息要 \(update\) 。
2. 树上一条路径的信息，下层更新之前要保证上层信息正确。所以往下递归前要 \(pushdown\) ，这可以确保 \(settag\) 时的信息就是当前路径上的真实信息。
   • 线段树延迟标记的原理即 \(modify\) 和 \(query\) 的路径信息都是真实的，而不在乎其他路径。
     • 显然与普通线段树的区别只在于 \(lazy\ tag\) 的构建、\(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);
	}
}

不难发现

1. 单点修改线段树与打标记线段树几乎没有差距。存在 \(change\) 和 \(modify\) 函数的不同、\(query\) 递归前需要 \(pushdown\) 。
2. 线段树只需要一个框架，关键是确定需要的信息、标记、其间合并方式。

完整代码

#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;
}

本栏目推荐文章
• 线段树练习
• 李超线段树
• Unlocking the Road to Success: The Benefits of Online Driver's Education
• 数据结构 - 线段树学习笔记
• [Noi Online #1 入门组] 跑步 题解
• 浅谈几类线段树、树状数组优化 DP
• 1000: 【编程入门】熟悉一下Online Judge的环境
• 线段树
• P3372 【模板】线段树 1
• P10009 [集训队互测 2022] 线段树 题解

线段 打标 Daimayuan Online Judge线段 打标daimayuan online 线段daimayuan online judge 环境online judge 1000 语言 环境online judge daimayuan judge daimayuan技巧252 everywhere sparser judge whole 打标 daimayuan 249 dp