什么是差分数组？如何 O(1) 完成区间批量加？

简化版

差分数组是前缀和的逆运算,专治「多次区间批量加、最后统一查询」。diff[i] = a[i] - a[i-1]。要给区间 [l, r] 的每个元素都加 val,只需两次修改:diff[l] += val、diff[r+1] -= val,O(1)。所有区间操作做完后,对 diff 求前缀和就还原出最终数组。把 m 次区间更新从 O(mn) 降到 O(m + n)。

详细版

// 原数组 a，差分数组 diff[i] = a[i] - a[i-1]（diff[0] = a[0]）
int[] diff = new int[n + 1];           // 多留一位防 r+1 越界

// 区间 [l, r] 全部加 val：只改两个端点，O(1)
void rangeAdd(int l, int r, int val) {
    diff[l] += val;
    diff[r + 1] -= val;                 // r+1 处减掉，抵消 r 之后的影响
}

// 所有操作做完后，前缀和还原出结果数组
int[] restore() {
    int[] res = new int[n];
    res[0] = diff[0];
    for (int i = 1; i < n; i++)
        res[i] = res[i - 1] + diff[i];  // 前缀和还原
    return res;
}

diff[l] += val:从 l 开始,后面都被抬高 val。
diff[r+1] -= val:到 r+1 处抵消,使影响只作用于 [l, r]。
前缀和还原:res[i] = res[i-1] + diff[i],把差分变回原值。

完整版教学

一、差分是前缀和的逆运算

前缀和:由原数组算「累加和」。差分:由原数组算「相邻差」,diff[i] = a[i] - a[i-1]。两者互逆——对差分数组求前缀和,就还原出原数组:

res[i] = diff[0] + diff[1] + ... + diff[i]
       = a[0] + (a[1]-a[0]) + (a[2]-a[1]) + ... = a[i]   （中间全抵消）

这个「差分 ↔ 前缀和」的互逆关系是理解差分的钥匙:前缀和把「区间查询」变 O(1),差分把「区间更新」变 O(1),它俩是一对。

二、核心:区间加只需改两个端点

差分的威力在于「区间批量加」只要改两个位置。要给 [l, r] 每个元素加 val:

diff[l] += val:在差分数组的 l 处 +val。还原(前缀和)时,从 l 开始的所有元素都会被抬高 val。
diff[r+1] -= val:在 r+1 处 -val。还原时,从 r+1 开始又被压低 val,正好抵消——于是 val 的影响被精确限制在 [l, r] 区间内。

一次区间加只改两个数,O(1);不管区间多长都一样。这是差分最核心的性质。

三、为什么这样能限定影响范围

从「前缀和还原」的角度看:res[i] = diff[0] + ... + diff[i]。diff[l] += val 意味着「从 l 往后每个 res 都多加了 val」;diff[r+1] -= val 意味着「从 r+1 往后每个 res 又减了 val」。两个效果叠加:

i < l:两个改动都没影响,res[i] 不变。
l <= i <= r:只受 +val 影响,res[i] 加了 val。✓
i >= r+1:+val 和 -val 抵消,res[i] 不变。✓

正好实现了「只给 [l, r] 加 val」。记住 [l] += val, [r+1] -= val 这个定式。

四、适用场景:多次区间更新 + 最后查询

差分的典型使用模式是:

先积累所有区间更新:m 个操作,每个 rangeAdd(l, r, val) 都是 O(1),共 O(m)。
最后一次前缀和还原:O(n) 得到最终数组。

总共 O(m + n),而朴素做法「每次区间加都遍历区间」是 O(mn)。所以差分适合「更新很多、且更新集中在前面、查询在后面」的场景。注意:差分不适合「更新和查询交替进行」(每次改完立刻要查),那种用树状数组/线段树。

五、经典应用

航班预订统计(LeetCode 1109):每个预订是一个区间加座位数,差分 + 还原。
拼车(LeetCode 1094):上下车看成区间 [start, end) 加减乘客,判断是否超载。
区间加法、会议室人数统计、统计每个时刻的在线人数等,凡是「大量区间 ± 某值,最后看每个位置的值」都用差分。

六、和前缀和、树状数组的关系

工具	擅长	复杂度
前缀和	静态数组、区间查询	预处理 O(n)、查询 O(1)
差分	区间批量更新 + 最后查询	更新 O(1)、还原 O(n)
树状数组/线段树	更新与查询交替	单点/区间改查都 O(log n)

前缀和管「查」、差分管「改」,两者互逆、场景互补;既要频繁改又要频繁查,才上树状数组/线段树。

七、从公式证明到手算闭环

这道题成立的核心是：diff[i] 记录当前位置相对前一位置的增量，区间起点开启影响，终点后一位关闭影响。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。

diff[0] = a[0]
diff[i] = a[i] - a[i-1]
add(l,r,v): diff[l] += v; if r+1<n: diff[r+1] -= v
a[i] = a[i-1] + diff[i]

带数字推演：零数组长度 5，对 [1,3] 加 2 后 diff 为 [0,2,0,0,-2]，前缀恢复为 [0,2,2,2,0]。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。

核对维度	本题结论
正确性依据	`diff[i]` 记录当前位置相对前一位置的增量，区间起点开启影响，终点后一位关闭影响
复杂度	每次区间更新 O(1)，最终还原 O(n)，额外空间 O(n)
关键边界	右端点后一位可能等于 n；差分适合多次更新后统一还原，不适合更新与区间查询交错的在线场景

记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。

八、实现边界与测试策略

实现时最需要警惕的是：右端点后一位可能等于 n；差分适合多次更新后统一还原，不适合更新与区间查询交错的在线场景。这不是语法细节，而是决定算法是否仍满足题目语义的前提。

提交前应分别验证：

空数组或最小合法规模，确认哨兵位置和初始化。
查询或更新紧贴左、上边界，确认没有访问负下标。
查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
包含 0、负数或重复前缀的样例，确认频次与取模语义。
大数输入，确认累计和、乘积或答案数量的整数类型足够。

如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。

九、常见误区与追问

误区：diff[r] 减 v 就能结束区间影响。 闭区间 [l,r] 应在 r+1 处关闭影响。
误区：差分更新后原数组立即可查。 需要做一次前缀累加才得到最终值。
误区：差分可以高效回答任意区间和。 裸差分擅长区间更新，不直接提供在线区间查询。
追问：为什么两个端点就够？ 前缀恢复会把起点增量向后传播，负增量在 r+1 抵消传播。
追问：更新和查询交错怎么办？ 使用树状数组或带懒标记的线段树。
追问：能否在原数组上构造？ 可以从右向左做 a[i]-=a[i-1]，避免覆盖尚未使用的前值。

十、加强记忆

差分数组是前缀和的逆运算(diff[i]=a[i]-a[i-1],对差分求前缀和还原原数组)。核心:区间 [l,r] 加 val 只需 diff[l]+=val; diff[r+1]-=val,O(1)——l 处抬高、r+1 处抵消,把影响限定在区间内。多次区间更新后一次前缀和还原,总 O(m+n)(朴素 O(mn))。适合「大量区间加、最后查询」(航班预订、拼车);改查交替用树状数组/线段树。前缀和管查、差分管改,互逆互补。

简化版

详细版