举例

考虑数组 $a = [2, 3, 5, 6, 8]$，对其中相邻元素两两做差（右边减左边），得到数组 $[1,2,1,2]$。然后在开头补上 $a[0]$，得到差分数组
$$
d = [2,1,2,1,2]
$$
这有什么用？如果从左到右累加 $d$ 的元素，即可「还原」回 $a$ 数组 $[2, 3, 5, 6, 8]$。

更进一步，现在把连续子数组 $a[1], a[2], a[3]$ 都加上 $10$，得到 $a^{‘} = [2,13,15,16,8]$。再次两两做差，并在开头补上 $a^{‘}[0]$，得到差分数组
$$
d^{‘} = [2,11,2,1,-8]
$$
对比 $d$ 和 $d^{‘}$，可以发现对 $a$ 中连续子数组的操作，可以转变成对差分数组 $d$ 中两个数的操作。

定义和性质

对于数组 $a$，定义其差分数组（difference array）为
$$
d(i) =
\begin{cases}
a[0], & i = 0 \
a[i] - a[i - 1], & i \geq 1
\end{cases}
$$
性质1：从左到右累加 $d$ 中的元素，可以得到数组 $a$。

性质2：以下两个操作是等价的。

  • 区间操作：把 $a$ 的子数组 $a[i],a[i + 1],\ldots,a[j]$都加上 $x$。
  • 单点操作：把 $d[i]$ 增加 $x$，把 $d[j + 1]$ 减少 $x$。特别地，如果 $j + 1 = n$（$n$为数组长度），则只需把 $d[i]$ 增加 $x$。

利用性质2，我们只需要 $O(1)$ 的时间就可以完成数组 $a$ 上的区间操作。最后利用性质1从差分数组复原出数组 $a$。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* 你有一个长为 n 的数组 a，一开始所有元素均为 0。
   给定一些区间操作，其中 queries[i] = [left, right, x]，
   你需要把子数组 a[left], a[left+1], ... a[right] 都加上 x。
   返回所有操作执行完后的数组 a。*/
int[] solve(int n, int[][] queries) {
    int[] diff = new int[n]; // 差分数组
    for (int[] q : queries) {
        int left = q[0], right = q[1], x = q[2];
        diff[left] += x;
        if (right + 1 < n) {
            diff[right + 1] -= x;
        }
    }
    for (int i = 1; i < n; ++i) {
        diff[i] += diff[i - 1]; // 直接在差分数组上复原数组 a
    }
    return diff;
}