advanced · lazy propagation

区间修改：懒标记 lazy propagation

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

当一个节点的 [lo,hi] 被修改区间完全覆盖时：它那段的和可以一次性加好 ( $val += d \times 段长$ )，但它欠下面所有孩子各一份 d。与其立刻递归到底去逐个通知（又是 $O(n)$ ），不如在这个节点上挂一个 lazy 标记记下「这片欠加 d」， 到此为止，不再下传。
只有等到下次真的需要走进它的孩子时（后续的查询 / 修改路过这里），才把欠账 下推 (push-down) 给左右孩子。如此，区间修改与区间查询都稳稳停在 $O(\log n)$ 。下图节点上的 +d 虚线框就是挂着的 lazy 标记。

1 · push-down 到底搬了什么？

pushDown(node) 做的事：若 $node.lazy = t \ne 0$ ，就给两个孩子各自 $child.val += t \times 孩子段长$ 、child.lazy += t，然后清空 node.lazy。标记像水一样，只在被需要时往下渗一层。所以一个挂在高处的 lazy，可能很久都不动—— 直到某次操作的路径正好穿过它。这就是「lazy」的含义：把更新推迟到必要时才执行，避免提前做无用功。

动手验证延迟下传：先做一次 add([1,5], 3)，看标记挂在了哪几个高节点上、底下叶子还没变; 再做一次 query([3,7])，看路径经过那些挂标记的节点时，标记如何被逐层下推、叶子的真值这才浮现。

2 · 实际应用

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