本文部分内容借鉴自 OI-Wiki
懒标记的含义及必要性
P3372 【模板】线段树 1
给定一个长为 \(n(n\le 10^5)\) 序列，\(m(m\le 10^5)\) 次操作，每次操作为：
- 区间 \([l,r]\) 中的数每个加 \(k\)。
- 询问区间 \([l,r]\) 的区间和。
考虑使用线段树完成此问题。每次修改，我们需要对在本区间内的 \(O(n)\) 个节点进行修改，这样的时间复杂度显然无法接受。我们发现，进行的部分修改并没有在询问中用到，因此，我们考虑引入懒标记来进行延迟修改。
考虑在没有懒标记的时候，每个节点的操作序列，懒标记实际上是截断并合并了节点的一段后缀操作序列，只在访问当前节点的时候，才将这些操作的影响施加于当前节点。对于每个节点，我们除区间和外，记录以下内容：在该节点代表的区间内进行的加法，且并未对其子节点进行修改的 \(k\) 的和。每次修改及询问，当需要访问该节点的子节点的时候，我们将这些懒标记下放（即只在必要的时候进行对子节点信息的修改），并将当前懒标记清零。
在这样的情况下，我们每次对节点的修改都需要同时对记录的值，及懒标记进行修改，这就涉及到一个懒标记的合并（及操作序列的合并）问题。
在本题中，由于只有区间加法，懒标记的合并是简单的。
下面，我们来看一道更难的题目：
P3373 【模板】线段树 2P3372 【模板】线段树 1
给定一个长为 \(n(n\le 10^5)\) 序列，\(m(m\le 10^5)\) 次操作，每次操作为：
- 区间 \([l,r]\) 中的数每个加 \(k\)。
- 区间 \([l,r]\) 中的每个数乘上 \(k\)。
- 询问区间 \([l,r]\) 的区间和。
在本题中，需要处理加法，乘法的懒标记合并问题，考虑加法及乘法对于节点值、其他懒标记的影响即可。注意，在考虑对于其他懒标记的影响的时候，必须先钦定懒标记生效的顺序，然后再去考虑其二者间的影响。对于不同的顺序，影响一般是不同的。
和上一道相似的一道题：
P1253 扶苏的问题
给定一个长为 \(n(n\le 10^6)\) 序列，\(m(m\le 10^6)\) 次操作，每次操作为：
- 区间 \([l,r]\) 中的数每个加 \(k\)。
- 区间 \([l,r]\) 中的每个数都变为 \(k\)。
- 询问区间 \([l,r]\) 的区间和。
钦定两个操作的懒标记生效顺序，考虑影响，然后合并即可。
更难的一道题：
P4314 CPU 监控
给定一个长为 \(n(n\le 10^6)\) 序列，\(m(m\le 10^6)\) 次操作，每次操作为：
- 区间 \([l,r]\) 中的数每个加 \(k\)。
- 区间 \([l,r]\) 中的每个数都变为 \(k\)。
- 询问区间 \([l,r]\) 的区间最大值。
- 询问区间 \([l,r]\) 的历史区间最大值。
考虑在坐标系中画出每个懒标记的变化曲线，考虑什么会成为最大值，及懒标记的合并问题。
愿此行，终抵群星。