advanced · lazy propagation

懒标记与区间修改

线段树一页的修改是单点的。可现实里常要「把一整段 [l, r] 都加上 d」—— 若逐个叶子修改，一次区间修改就退化成 $O(n)$ ，之前的优势全部丢失。 懒标记 (lazy propagation) 的核心是延迟执行：把欠下的修改记在节点上，需要时才下传。

注 · 当一个节点的 $[lo, hi]$ 被修改区间完全覆盖时，它那段的聚合值可以一次性算好（区间加时是 $val \mathrel{+}= d\,(hi-lo+1)$ ），但它欠下面所有孩子各一份 $d$ 。与其立刻递归到底逐个通知（又是 $O(n)$ ），不如在这个节点上挂一个 lazy 标记记下这笔欠账，到此为止不再下传；等下次真的需要走进它的孩子时（后续的查询或修改途经该节点），才把欠账下推（push-down）给左右孩子。区间修改与区间查询于是都停在 $O(\log n)$ 。

警示 · 这套办法对标记本身有要求：标记必须可复合（同一节点上先后挂的两个标记能合成一个），且能在 $O(1)$ 内按段长作用到节点的聚合值上。混用「区间赋值」与「区间加」时两类标记不可交换，必须定序——赋值要清掉尚未下推的加法标记，否则下推顺序一变结果就变。

图 0-1 · 节点上的 +d 虚线框即挂着的 lazy 标记。可单步执行区间加与区间查询，观察标记挂在哪几个节点、又在哪一步被下推。

1 · push-down 搬运的内容

注 · pushDown(node) 做的事：若 $node.lazy = t \ne 0$ ，就给两个孩子各自把 $val$ 加上 $t$ 乘以自己的段长、把 $lazy$ 加上 $t$ ，然后清空 node.lazy。标记只在被需要时往下渗一层，所以一个挂在高处的 lazy 可能很久都不动，直到某次操作的路径正好穿过它。

警示 ·「底下叶子还没变」这句话要看是哪个「值」。默认数据上做 add([1,5], 3) 后，实测标记只挂在 $[1,1]$ 、 $[2,3]$ 、 $[4,5]$ 三处（其中 $[1,1]$ 本身就是叶子），而数组视图里 $[1,5]$ 的叶子显示值已经全部加好——因为 lazyLeafDisplay 把祖先尚未下推的 lazy 折算进了叶子的显示值。真正没变的是树节点的 val 字段，它要等下一次操作路过时才被 push-down 补上。

2 · 实际应用

扫描线求矩形面积并 / 周长并（区间 +1/−1 配合查询）、区间赋值 + 区间和/最值、 区间反转、区间乘加（两类标记的复合次序要定死）、游戏里大范围地形与光照的批量更新。凡是「整片地改、整片地问」，lazy 都是把它压到对数级的关键手段。