懒惰传播 | Codeboy's Blog

形式陈述

设线段树节点摘要取值于集合 $X$ ，待处理更新标签构成幺半群 $(T,\circ,e)$ ，并通过幺半群作用

\alpha:T\times X\to X

作用于摘要。这里 $t_2\circ t_1$ 表示先执行 $t_1$ 、再执行 $t_2$ ；实现中的标签复合顺序必须与这一约定一致。

若一次更新完整覆盖节点区间 $I$ ，就把摘要改为 $\alpha(t,s_I)$ ，并把节点标签复合为 $t\circ lazy_I$ 。访问子节点前，将父标签作用到两个孩子并清空父标签。正确性至少需要：

标签作用满足单位元与结合复合律；
节点摘要包含足够局部信息，使 $\alpha(t,s_I)$ 可在 $O(1)$ 时间计算；
同一标签对左右摘要合并兼容，通常写成 $\alpha(t,x\oplus y)=\alpha(t,x)\oplus\alpha(t,y),$ 或把区间长度等元数据纳入 $x,y$ 后使该式成立；
查询、下传与标签复合始终遵守同一时间顺序。

在这些条件下，标准区间更新与区间查询各访问 $O(\log n)$ 个规范节点，最坏时间为 $O(\log n)$ 。

直觉

Lazy propagation 把“整段仍欠一次变换”记录在内部节点，而不立即逐叶执行。只要查询仍完整覆盖该节点，摘要已经足够回答；只有进入子区间时才兑现欠账。

关键不是多一个 lazy 数组，而是建立一套闭合代数：标签能复合，标签能直接更新整段摘要，且先后次序不会在父子层之间改变。任何一项缺失，延迟执行都可能与立即执行产生不同结果。

例子与边界

区间加、区间和可令摘要为 $(s,\ell)$ ，标签为 $v\in(\mathbb R,+,0)$ ：

v\cdot(s,\ell)=(s+v\ell,\ell).

两个加法标签直接相加，单位标签为 $0$ 。把长度放进摘要后，作用与左右合并兼容。

区间赋值标签可表示为 none 或 assign(c)。后来的赋值覆盖早先赋值，因此复合不交换。若同时支持赋值与加法，标签可规范化为仿射变换 $x\mapsto ax+b$ 的受限子幺半群；复合时顺序写反会在混合操作上产生错误。

区间取模、依赖元素分布的条件更新或“把每个值替换为其排名”通常不能仅由常数大小摘要计算整段新值。Segment Tree Beats 等方法依赖更丰富不变量与摊还分析，不是普通 lazy tag 的直接实例。

推论与应用

函数复合是理解标签顺序的实现工具，幺半群作用则给出不依赖具体代码的正确性接口。搜索树增强只要求摘要可由孩子恢复；lazy propagation 还要求更新作用与摘要合并相容，是更强的维护契约。

持久化线段树中，下传会修改孩子，因此必须路径复制，不能污染旧版本。并行或无锁实现还需处理多个标签的同步顺序；代数可合成不代表并发写入自动线性化。

参考资料

Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, augmented tree invariants.
AtCoder Library, “Lazy Segtree,” algebraic interface documentation, 2026.
OI-Wiki contributors, “Lazy Segment Tree,” 2026.