用于区间更新的差分数组
快速执行多次区间加法操作
用于区间更新的差分数组 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
换个角度处理问题
前缀和可以快速回答范围 query。差分数组则从相反方向出发，可以快速执行许多范围更新。🔁
低效的方法
每次将一个值加到范围内的每个元素上，都会花费 O(n)；重复许多次后，每次更新的开销都会累积。进行 q 次更新时，这个开销会急剧增加。
记录变化
不要修改每个单元格，而只记录变化开始的位置和结束的位置。请标记边界，而不是中间的每个位置。
差分数组的内容
差分数组存储每个元素与前一个元素之间的差值。修改一个差值，就会使后面的一整段发生偏移。
两个标记技巧
要将 v 加到 l 到 r 的范围，请在索引 l 处加上 v，并在索引 r + 1 处减去 v。只需两次修改，就能覆盖整个范围。
diff[l] += v
diff[r + 1] -= v为何要减去
l 处的加法会开启这次变化；r + 1 处的减法会将其关闭。两者结合，就能把更新限制在一个范围内。
低成本应用所有更新
每次更新只需写入数组两次，因此 q 次更新总共只需 O(q)。真正繁重的工作会推迟到最后完成。
还原最终数组
放置完所有标记后，请对差分数组计算一次前缀和。这次遍历就能重建每个最终值。
for i in range(1, n):
diff[i] += diff[i - 1]用防护位确定大小
将数组长度增加一个单元，这样 r + 1 就永远不会越过末尾。这个额外的防护位置可以避免索引错误。
总开销
您需要花费 O(q) 标记更新，再进行一次 O(n) 遍历来重建数组。合计开销远低于朴素的 O(n × q)。
优势所在
差分数组非常适合计算预订数量、道路通行费，以及任何包含大量范围加法操作并只需最后读取一次结果的问题。
快速检查
您需要将 v 加到从索引 l 到 r 的每个元素上。
总结
您可以使用差分数组批量处理范围更新：标记 l 和 r + 1，然后只计算一次前缀和来重建数组。更新快速，最后统一读取一次。✅
常见问题解答
「用于区间更新的差分数组」课时是免费的吗？
是的 — 「用于区间更新的差分数组」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 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 反馈 — 无需本地设置。
此课程中的所有课时
- 构建前缀和数组
- 使用减法求任意区间和
- 统计目标和子数组
- 用于区间更新的差分数组