01先把问题说具体
对长度 n 的数组执行很多次区间加,最后只查询一次最终数组,怎样避免每次遍历整个区间?
02一步步得到方法
差分记录相邻位置的变化
定义 d[0]=a[0],d[i]=a[i]−a[i−1]。从左到右累加 d 就能还原 a,因为中间相邻项抵消。差分与前缀和是一对相反操作。
对半开区间 [l,r) 加 x,只有进入 l 时的增量增加 x,离开 r 时的增量减少 x;区间内部相邻两项都加 x,差值不变。
把更新与查询阶段分开
额外开一个 n+1 长度数组,允许在 r=n 写停止事件。所有更新只做两个写入,最后统一前缀累加。若每次更新后都要求查询某位置,则这个离线方案的优势会减弱,需要树状数组等结构。
用一增一减描述影响的开始和结束
对半开区间 [l,r) 加 v,可以在差分 l 处加 v、r 处减 v。还原时前缀累计进入 l 后携带 v,进入 r 时抵消;这把“所有位置分别改”压缩为两个事件。
差分适合批量更新后统一读取最终结果。若每次修改后都要立即查询许多不同区间,反复完整还原仍很贵,需要结合前缀技巧或动态范围数据结构。
03把一个小例子完全算清楚
初始全零、长度 5;[1,4) 加 3,再 [2,5) 加 2。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 第一条事件 | d=[0,3,0,0,-3,0] | 在 1 开始、4 停止 |
| 第二条事件 | d=[0,3,2,0,-3,-2] | 在 2 开始、5 停止 |
| 前缀累加 | [0,3,5,5,2] | 两条更新在 2、3 叠加 |
窄屏可左右滑动表格,阅读完整计算与理由。
只修改端点,最后一次扫描把事件展开成各位置的累计影响。
04为什么这个方法成立
- 一个区间的 +x 事件使从 l 起的前缀都增加 x。
- r 处的 −x 抵消 r 及之后的变化,因此影响恰好覆盖 [l,r)。
- 多个更新线性叠加,与逐区间逐格执行等价。
05把推导翻译成代码
Python · 可独立运行的教学实现
def range_add(a, updates):
n = len(a)
d = [0] * (n + 1)
for left, right, value in updates:
assert 0 <= left <= right <= n
d[left] += value
d[right] -= value
result, change = [], 0
for i, value in enumerate(a):
change += d[i]
result.append(value + change)
return result逐个理解关键决定
d[right] -= value- 停止点不属于更新区间;闭区间 [l,r] 应改在 r+1 停止。
value + change- 这里的 d 只保存增量,最终叠加原数组,而非直接把增量当结果。
06时间、空间与实现范围
q 次更新加一次还原,总时间 O(n+q),额外空间 O(n)。
若每次更新后都还原,时间又会变为 O(nq),因此要先识别离线需求。
07改变条件,检查哪里会出错
只写起点,不写终点
更新会错误延伸到数组结尾。
区间终点越界
若采用闭区间 [l,r],抵消点是 r+1;通常需要额外哨兵槽或显式边界判断。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
[2,2) 加 9 会改变什么?
需要一点提示
两个事件在同一位置。
查看解析与答案
互相抵消,空区间不改变任何值。
如何做区间减 4?
需要一点提示
增量允许负数。
查看解析与答案
传入 value=−4,端点规则不变。
二维矩形加应写几个事件?
需要一点提示
对两轴分别应用开始和停止。
查看解析与答案
四个角,符号为 +、−、−、+,最后做二维前缀还原。