区间更新的延迟传播
延后对整个区间执行更新
区间更新的延迟传播 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
区间更新问题
如果查询要求将从 l 到 r 的每个元素都加 5，该怎么办？每次更新都访问每个叶节点需要 O(n) 时间，处理大量区间更新时远远不够快。😰
延迟处理的思想
延迟传播允许节点记住尚未处理的变更，而不必立即将其传给子节点。只有真正需要访问这些子节点时，才会执行这项工作。
为待处理工作添加第二个数组
除了树本身，我们还要维护一个延迟标记数组。它保存应用于某个节点整个区间、但尚未向下传递的更新。
lazy = [0] * (4 * n)应用到整个节点
当一次更新完全覆盖某个节点时，请调整该节点保存的值，并将这项变更累积到延迟标记中，然后停止。无需继续向下遍历。
seg[node] += (r - l + 1) * val
lazy[node] += val向下遍历前先下推
访问子节点之前，请将所有待处理的延迟值下推到两个子节点中。这样，您读取子节点时，它们就能保持正确。
def push_down(node, l, r):
if lazy[node]:
apply(2*node, l, mid)
apply(2*node+1, mid+1, r)
lazy[node] = 0每个节点的三种情况
在每个节点处，查询区间可能与它不相交、完全覆盖它，或仅部分覆盖它。相应地执行跳过、延迟应用，或递归处理两半。
延迟更新保持对数级
区间更新只会访问 O(log n) 个节点，因为完全覆盖的节点会提前停止。这就是采用延迟处理的全部收益。⚡
查询也要下推
区间查询在递归之前也必须下推，这样才能读取子节点的最新值。忘记这一步是惰性传播中最典型的错误。
递归后向上合并
更新子节点后，请根据它们重新合并父节点。这样的向上合并可以让每个内部节点始终与其子树保持一致。
seg[node] = seg[2*node] + seg[2*node+1]赋值与加法
惰性传播适用于许多操作，但赋值和加法的合并方式不同。在编码之前，请先确定两个待处理更新应如何合并。
何时值得使用惰性传播
只有在确实需要区间更新时，才应使用惰性传播。若只需进行单点更新，普通线段树更简单，也已经足够。
快速检查
在递归进入节点的子节点之前，必须做什么？
回顾：延迟更新
您已经学会了惰性传播：存储待处理的变更，向下遍历前进行下推，之后向上合并，从而实现 O(log n) 的区间更新。🎉
用 AI 导师学习 Coding Interview Prep — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 90
- 课程
- 360
常见问题解答
「区间更新的延迟传播」课时是免费的吗？
是的 — 「区间更新的延迟传播」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「区间更新的延迟传播」这节课中我会学到什么？
延后对整个区间执行更新 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「区间更新的延迟传播」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 用于前缀和的树状数组
- 使用 BIT 计算逆序对
- 线段树：构建与查询
- 区间更新的延迟传播