专题进阶 · 数组技巧推荐总顺序 · 第 39 / 148 课

将区间加拆成两个端点事件,再用前缀和还原全部变化。

先学会这些,再进入本课 前缀和
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数组技巧

差分Difference Array

把区间加转换为两个端点的改动,最后前缀累加还原。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

将区间加拆成两个端点事件,再用前缀和还原全部变化。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 一个区间的 +x 事件使从 l 起的前缀都增加 x。
  2. r 处的 −x 抵消 r 及之后的变化,因此影响恰好覆盖 [l,r)。
  3. 多个更新线性叠加,与逐区间逐格执行等价。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[2,2) 加 9 会改变什么?

需要一点提示

两个事件在同一位置。

查看解析与答案

互相抵消,空区间不改变任何值。

练习 2 · 边界与辨析

如何做区间减 4?

需要一点提示

增量允许负数。

查看解析与答案

传入 value=−4,端点规则不变。

练习 3 · 变式与迁移

二维矩形加应写几个事件?

需要一点提示

对两轴分别应用开始和停止。

查看解析与答案

四个角,符号为 +、−、−、+,最后做二维前缀还原。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。