差分数组 | Codeboy's Blog

形式陈述

设长度 $n\ge1$ 的数组 $a_1,\ldots,a_n$ 的元素属于加法交换群，零元记为 $0$ ，减法表示加上逆元。固定 $a_0=0$ ，定义

d_1=a_1,\qquad d_i=a_i-a_{i-1}\ (i>1).

对合法区间 $1\le l\le r\le n$ 全部加 $x$ ，只需令 $d_l\mathrel{+}=x$ ，若 $r<n$ 再令 $d_{r+1}\mathrel{-}=x$ 。最终对 $d$ 取前缀和即可恢复更新后的序列，因为

\sum_{j=1}^{i}d_j=a_1+(a_2-a_1)+\cdots+(a_i-a_{i-1})=a_i.

在固定零边界、有限数组和交换群这一共同范围内，差分与前缀累积互为逆变换；这里的等价关系不包含只有幺半群结构的一般前缀聚合。初始化与最终恢复各需 $O(n)$ 次运算， $q$ 次区间加只需 $O(q)$ 次端点修改，总计 $O(n+q)$ 次群运算和槽访问；元素及运算为常数成本时，就是 $O(n+q)$ 时间和 $O(n)$ 空间。空数组不接受非空区间更新，直接返回空结果。

直觉

差分数组存储相邻前缀状态之间的增量，而不是每个位置的绝对值。区间统一加上 $v$ 时，内部相邻元素同时增加，差值彼此抵消，只有左端加 $v$ 、右端后一位减 $v$ 的边界变化留下；最后一次前缀累积恢复全部元素。这个技巧本质上是离散微分与离散积分的互逆。

例子与边界

原数组 $[1,3,3,5]$ 的差分可写为 $[1,2,0,2]$ 。对区间 $[2,3]$ 加 $4$ ，修改 $d_2{+}=4$ 、 $d_4{-}=4$ ，得到 $[1,6,0,-2]$ ；前缀恢复时依次得到 $1$ 、 $1+6=7$ 、 $7+0=7$ 、 $7-2=5$ 。这里 $d_3$ 不变，是因为更新后 $a_3-a_2=(3+4)-(3+4)=0$ ； $d_4$ 减少，是因为 $a_4$ 没增加而 $a_3$ 增加了。

若区间一直更新到 $r=n$ ，无需修改数组外的位置；若使用 $n+1$ 个槽的哨兵实现，也应只恢复前 $n$ 项。多个更新可以直接叠加到同一差分数组，中间不必恢复。

差分适合离线积累大量区间更新，并在线性时间统一恢复。若更新与查询交错，直接求某项仍需累加一个前缀，最坏 $O(n)$ ；要降低查询成本，可把差分存入 Fenwick 树或线段树。普通差分要求更新是可组合、可逆的加法作用；在一般交换幺半群上只有前缀聚合而未必存在差分。

推论与应用

差分连接离散导数与前缀积分：前缀和是恢复操作，交换群提供加法逆元，数组提供可寻址的有界坐标域。它支撑扫描线事件和区间更新批处理；二维差分可把矩形更新化为四个角点修改，在线场景则通过两个Fenwick 树实现区间加与前缀/区间和。前缀恢复也可用并行 scan 或按块顺序读取，但工作、深度和 I/O 必须在各自模型中另计。

差分数组并不是一般数据流摘要：它需要为每个端点保留可寻址槽位，并在最后完整扫描。数据流分位数面对可能巨大或未知的值域，只用受限空间近似秩查询，通常显式带误差与失败概率；两者都“顺序处理更新”，却在存储假设、输出语义和保证类型上完全不同。

参考资料

Antti Laaksonen, Competitive Programmer’s Handbook, 2018，Ch. 9 “Range queries” 的 “Range updates”，pp. 93–94。
Donald E. Knuth, The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997, cumulative sums and finite differences.

形式陈述 ​

反向链接

形式陈述