Lazy Propagation

释义 Definition

“Lazy propagation”（懒惰传播/延迟下传）是数据结构（常见于线段树 Segment Tree）中的一种优化技巧：对区间更新时，先把“需要更新的信息”暂存在父节点（打标记），等到必须访问子区间（查询或继续细分更新）时再把标记下传，从而避免每次都立刻更新到所有子节点，提升效率。

发音 Pronunciation（IPA）

/ˈleɪzi ˌprɑːpəˈɡeɪʃən/

例句 Examples

Lazy propagation makes range updates much faster.
延迟下传会让区间更新快得多。

In a segment tree, lazy propagation stores pending updates at internal nodes and pushes them down only when a query needs deeper information.
在线段树中，延迟下传会把“待更新”的信息暂存在内部节点，只有当查询需要更深层的数据时才把更新下推到子节点。

词源 Etymology

“Lazy”本义是“懒的”，在算法语境里引申为“不急着做、先拖着”，表示把工作延后到必要时再执行；“propagation”意为“传播/传递”。合起来就是“把更新信息延迟传递到子节点”的策略。该术语主要流行于算法竞赛与工程实现的讲解中。

相关词 Related Words

• Segment Tree
• Range Update
• Range Query
• Deferred Update
• Fenwick Tree
• Binary Indexed Tree
• Propagation
• Recursion

文献与作品 Literary / Notable Works

• Competitive Programming（Steven Halim 等）：在区间查询/更新数据结构章节中常与线段树一起讲到延迟下传思想。
• *Competitive Programming 4 (CP4)*（Steven & Felix Halim）：以竞赛实现为导向，常用“lazy propagation”描述线段树区间操作优化。
• cp-algorithms（在线算法参考资料，Segment Tree 条目）：以“lazy propagation”作为标准术语讲解区间加、区间赋值等典型标记下传实现。