形式陈述

对序列 $a_1,\dots ,a_n$，定义

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

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

直觉

区间内部相邻元素同时增加，差值相互抵消；只有区间边界留下变化。

例子与边界

多次离线区间更新可在线性时间统一恢复。若更新不是可组合、可逆的加法作用，则普通差分表示不能直接使用。

推论与应用

它连接离散导数与前缀积分，并支撑二维差分、扫描线事件和区间更新批处理。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), difference arrays.
• cp-algorithms contributors, Algorithms for Competitive Programming (2026), prefix sums and difference techniques.