算法与数据结构 · 第 17 课
Lazy Propagation:区间加为什么不需要逐个修改叶子?
2026 年 11 月 5 日|第 3 周 · 第 4 天|讲授约 17 分钟(自测另计)
昨天用“路径复制”实现了单点赋值、历史版本区间和。今天换成另一个问题:一次给十万个连续位置都加 5,是否必须访问十万个叶子?答案是不用,但必须准确区分“当前节点已经算过的值”和“还没有通知孩子的变化”。
一、学习目标与模型(约 1 分钟)
学完应能:(1) 解释懒标记(lazy tag)的真正含义;(2) 写出区间加 ADD 和区间和 SUM;(3) 手工追踪两次重叠更新及一次查询的 PUSH;(4) 证明 sum/lazy 不变量与最坏 O(log n) 时间;(5) 说明为什么普通可变 Lazy Segment Tree 不自动具有昨天的持久化性质。
数组长度为 n≥1,下标从 0 开始,区间均为左闭右开 [l,r)。节点 v 覆盖 [v.L,v.R),长度 len(v)=v.R−v.L。操作 ADD([l,r),δ) 使该区间内每个元素都增加 δ;SUM([l,r)) 返回当前区间和。先研究可变(ephemeral)线段树,即只保留最新版本;数值运算假设不会溢出。
二、动机:整段操作的成本在哪里?(约 2 分钟)
设 A=[2,1,3,4,5,6,7,8],总和 36。若要给 [0,8) 的每个元素加 3:
普通单点更新做 8 次,时间 O(n log n);但根节点负责整个 [0,8),它已经知道区间长度为 8,根的 sum 直接加 3×8 即可。问题是:根的孩子还保留旧和,稍后如果询问 [0,4) 怎么办?
这就是懒标记解决的事:先正确维护当前节点的总和,把向孩子分发增量的工作延期到真正需要进入孩子时。
三、最关键的不变量:sum 已算,lazy 待下推(约 3 分钟)
每个节点保存 sum(v) 与 lazy(v)。含义分别是:
- sum(v):所有已经执行的更新作用后,[v.L,v.R) 的真实区间和。
- lazy(v):已经计入 sum(v)、但尚未传递给两个孩子的“每个元素增加多少”。
对内部节点,必须始终满足
[ \boxed{\operatorname{sum}(v)=\operatorname{sum}(v.left)+\operatorname{sum}(v.right)+\operatorname{lazy}(v)\cdot\operatorname{len}(v).} ]
注意:当 lazy(v)≠0 时,不能直接写 sum(v)=sum(left)+sum(right)。孩子的 sum 还没有包含这部分增量。叶节点没有孩子,sum 就是该位置的当前值;其 lazy 不需要再向下传递。
flowchart TD
R["节点 v:sum 已包含整段增量,lazy=+3"] --> L["左孩子:可能仍是旧 sum"]
R --> G["右孩子:可能仍是旧 sum"]
Q{"需要访问某个孩子?"} -->|否:完全覆盖| N["直接用 v.sum,暂不下推"]
Q -->|是:部分覆盖| P["PUSH:给两孩子 APPLY(+3),清零父 lazy"]
P --> L
P --> G
图中箭头表示逻辑上的延迟传播,不是说每次查询都会修改所有后代。
四、五个核心过程(约 3 分钟)
定义 APPLY(v,δ) 为“将 v 所覆盖的全部元素加 δ”;PUSH(v) 将父节点待传递的标记交给两个孩子;PULL(v) 从孩子重新计算父 sum。BUILD 与普通区间和线段树相同。
BUILD(A,L,R):
if R-L == 1: return Node(L,R,sum=A[L],lazy=0)
M = (L+R)//2
a=BUILD(A,L,M); b=BUILD(A,M,R)
return Node(L,R,sum=a.sum+b.sum,lazy=0,left=a,right=b)
APPLY(v,delta):
v.sum += delta * (v.R-v.L)
v.lazy += delta
PUSH(v):
if v 是叶子 or v.lazy == 0: return
APPLY(v.left, v.lazy)
APPLY(v.right,v.lazy)
v.lazy = 0 # v.sum 不变!
PULL(v): # 只在 v.lazy 已清零后调用
v.sum = v.left.sum + v.right.sum
ADD(v,ql,qr,delta):
if qr<=v.L or v.R<=ql: return # 不相交
if ql<=v.L and v.R<=qr:
APPLY(v,delta); return # 完全覆盖
PUSH(v) # 部分覆盖
ADD(v.left, ql,qr,delta)
ADD(v.right,ql,qr,delta)
PULL(v)
SUM(v,ql,qr):
if qr<=v.L or v.R<=ql: return 0
if ql<=v.L and v.R<=qr: return v.sum
PUSH(v) # 部分覆盖
return SUM(v.left,ql,qr)+SUM(v.right,ql,qr)
公开接口须验证 0≤ql≤qr≤n。查询一个空区间返回 0;整棵树只包含 n≥1 的数组元素。这里的 SUM 可能修改节点的表示(下推 lazy),但不改变数组的逻辑内容或任何区间的答案。
五、数值 Trace:重叠更新后,查询为什么要 PUSH?(约 3 分钟)
继续用 A=[2,1,3,4,5,6,7,8],总和 36。
操作 1:ADD([2,6),+3)。 树把它分解为完整覆盖的 [2,4)、[4,6)。这两处直接 APPLY:它们的 sum 分别从 7→13、11→17,lazy 都变为 +3。根 sum 从 36→48。
操作 2:ADD([0,4),+2)。 左孩子 [0,4) 被完整覆盖,其 sum 从 16→24、lazy 变为 +2;右孩子 [4,8) 保持 32。根 sum 变为 56。
此时(还没做部分区间查询):
[0,8) sum=56, lazy=0
├─[0,4) sum=24, lazy=+2
│ ├─[0,2) sum=3, lazy=0 ← 尚未收到 +2
│ └─[2,4) sum=13, lazy=+3 ← 尚未收到 +2
└─[4,8) sum=32, lazy=0
├─[4,6) sum=17, lazy=+3
└─[6,8) sum=15, lazy=0
操作 3:SUM([3,5))。 该区间跨越两个部分覆盖的分支。访问 [0,4) 时,必须把它的 +2 下推:[0,2) 的 sum 变为 7,[2,4) 的 sum 变为 17、lazy 由 +3 变为 +5;继续进入 [2,4) 时再把 +5 下推给两个叶子。访问 [4,6) 时,把 +3 下推,才能取得单个位置 [4,5) 的最新值。最后 [3,4) 为 9,[4,5) 为 8,故
[ \operatorname{SUM}([3,5))=9+8=17. ]
请注意:PUSH 之后父节点 sum 不变。它只是把已记入父节点的贡献记入孩子;重复加到父 sum 会算两次。
六、正确性证明:把更新分成三种覆盖情况(约 2 分钟)
BUILD 基例。 叶节点 sum=A[i],内部节点 lazy=0 且 sum 为两孩子和,不变量成立。
APPLY 保持不变量。 一次整段加 δ,真实区间和增加 δ·len;执行 sum+=δ·len 同步记录新值,孩子暂时不变,而 lazy+=δ 使内部节点的等式仍然成立。
PUSH 保持不变量。 设原 lazy=t,把两孩子各 APPLY(t)。孩子区间长度之和是父区间长度,因此两孩子 sum 合计增加 t·len(v);与此同时将父 lazy 清零,父 sum 完全不变,等式仍成立。
部分 ADD 正确。 先 PUSH 让父子同步,再递归修改两个不交叠的子区间;递归返回后 PULL,得到整个父区间的真实总和。完全覆盖直接 APPLY,不相交无须修改。对子区间长度归纳即可。
SUM 正确。 不相交返回 0,完全覆盖直接返回正确的 sum;只有部分覆盖才 PUSH 并递归,两孩子返回值之和恰是查询区间与当前节点交集上的总和。
七、为什么仍是最坏 O(log n)?(约 2 分钟)
一次连续区间 [ql,qr) 的边界只有两个:ql 和 qr。在线段树同一深度,部分重叠、需要继续分裂的节点至多两个;完全覆盖的其他节点直接 APPLY 或读 sum,不再展开。每层只访问常数个节点,树高 O(log n),因此两种操作都是最坏 O(1+log n),并非按区间长度逐点操作。
| 操作 | 最坏时间 | 空间 |
|---|---|---|
| BUILD | O(n) | O(n) 个节点;栈 O(log n) |
| ADD(连续区间加) | O(1+log n) | 额外栈 O(log n) |
| SUM(连续区间和) | O(1+log n) | 额外栈 O(log n) |
查询可能 PUSH,但每次 PUSH 仅更新两个孩子,仍是 O(1)。多个操作共享一棵可变树,故总节点数始终 O(n),不因操作次数增长。
八、边界反例、持久化提醒与下一课(约 1 分钟)
忘记 PUSH 的最小反例: A=[1,2],对 [0,2) 加 5。根 sum=13、lazy=5,而两个叶子还存 1 和 2。若直接对子节点递归求 [0,1) 而不处理父 lazy,就会错误地得到 1;正确值是 6。
与昨天的持久化版本不能直接混用。 昨天保存多个版本根,并让它们共享不可变节点;今天的 PUSH 和 APPLY 会原地修改节点。若直接在共享的孩子上 PUSH,旧版本会被污染。要支持“持久化 + 区间加”,必须在每次修改前路径复制相关节点(包括将被下推修改的孩子),或为只读查询携带祖先尚未下推的增量;不能简单把可变版代码套到旧根上。
下一课(2026-11-06,第 18 课):回滚并查集(Rollback DSU)。 我们将学习另一种保留历史状态的方式:记录修改日志并撤销,与今天的 lazy 标记和昨天的路径复制进行比较。
九、四级自测(100 分;首次不给答案)
四题分别考察 lazy 机制、数值 Trace、复杂度边界与持久化冲突、完整算法证明。前三题可客观判分,Lv4 按证明要点计分。课堂正文仅包含中立提示,不公布标准答案或解析。
Lv1|Lazy 标记的含义与正确性|15 分|预计 2 分钟|单选
区间加 / 区间和线段树中,某内部节点 v 表示长度为 len 的区间。一次操作恰好完整覆盖它,需给每个元素加 δ。下列哪种做法能正确延后孩子的更新?
A. 只修改 v.lazy+=δ,不修改 v.sum。 B. 执行 v.sum+=δ×len、v.lazy+=δ;以后需要访问孩子时再下推。 C. 只修改 v.sum+=δ,保持 v.lazy 不变。 D. 立即递归更新所有叶子,不可能使用懒标记保证正确。
中立提示:区分“该区间当前的真实总和”与“尚未传递到孩子的增量”。
Lv2|半开区间叠加与数值 Trace|20 分|预计 4 分钟|数值
初始 A=[1,2,3,4,5,6,7,8],下标从 0 开始。依次执行 ADD([2,6),+3)、ADD([0,4),+2),然后计算 SUM([3,6))。求最终区间和(数值)。
中立提示:两个更新区间有重叠;先确认 [3,6) 包含哪三个下标,再分别累计它们受到的增量。
Lv3|不变量边界、复杂度与持久化冲突|25 分|预计 4 分钟|多选
关于支持区间 ADD 与区间 SUM 的标准可变 Lazy Segment Tree,下列哪些说法成立?(多选)
A. 当树按中点平衡划分、一次 APPLY/PUSH 为 O(1) 时,单次连续区间 ADD 和 SUM 的最坏时间均为 O(log n)。 B. 如果父节点 lazy 非零,部分重叠查询可以不下推、不携带延迟量,直接对子节点求和,仍保证正确。 C. 节点 sum 已计入其自身 lazy 所代表的区间增量;lazy 表示尚未传到孩子的部分。 D. 若多个历史版本共享节点,直接在共享节点上执行可变 PUSH,可能破坏旧版本的查询结果。
中立提示:分别检查树的边界访问节点数、父子的摘要一致性,以及共享节点能否安全原地修改。
Lv4|算法设计、归纳证明、界与反例|40 分|预计 10 分钟|开放推导
设计长度 n≥1、下标从 0 开始的区间加 / 区间和线段树,区间均为半开 [l,r)。(a)(12 分)写出 BUILD、APPLY、PUSH、ADD、SUM 的伪代码,明确遇到无交、完全覆盖、部分覆盖时的动作。(b)(12 分)给出 sum/lazy 不变量,并通过归纳证明整段加、下推、部分更新与查询都正确。(c)(10 分)推导建树的时间和空间、单次 ADD/SUM 的最坏时间以及递归栈空间,解释为什么连续区间每层只有常数个边界节点。(d)(6 分)给出忘记 PUSH 导致部分查询错误的最小反例,并说明为什么不能把可变 PUSH 直接套到昨天的路径复制持久化树上。
中立提示:把 lazy 理解为尚未作用到孩子、但已经计入当前 sum 的“每元素增量”;下推前后父节点总和不应改变。
十、作答与反馈
回复 Lv1:选项;Lv2:数值与计算过程;Lv3:所有正确选项;Lv4:(a)–(d) 的证明。我会按 15/20/25/40 分逐题批改:80–100 分按原计划继续;60–79 分补针对性练习;低于 60 分先复习 APPLY/PUSH 和父子 sum 不变量。补练不改变自然日课号。