差分数组 | eleven26

问题背景

如果给你一个包含 5000 万个元素的数组，然后会有频繁的区间修改操作，比如让第 1 个数到第 1000万个数每个数都加上 1，而且这种操作是频繁的。

此时，很容易想到的办法就是从 1 遍历到 1000万，每个加上 1，但如果这种操作很频繁的话，效率就可能会非常低下。

差分数组原理

假设现在有一个数组，\(nums=\{0, 2, 5, 4, 9, 7, 10, 0\}\)

\(index\)	0	1	2	3	4	5	6	7
\(d[i]\)	0	2	5	4	9	7	10	0

那么差分数组是什么呢？

其实差分数组本质上也是一个数组，我们暂且定义差分数组为 \(d\)，差分数组 \(f\) 的大小和原来 \(d\) 数组大小一样，而且 \(f[i] = d[i] - d[i - 1]\)，(\(i\neq0\))。

它的含义是什么呢？就是原来数组 \(i\) 位置上的元素和 \(i-1\) 位置上的元素作差，得到的值就是 \(d[i]\) 的值。

所以，上面数组对应的差分数组值如下图所示：

\(index\)	0	1	2	3	4	5	6	7
\(d[i]\)	0	2	5	4	9	7	10	0
\(f[i]\)	0	2	3	-1	5	-2	3	-10

那么构造这个数组有什么意义呢？

现在我们有这么一个区间操作，即在区间 \([1,4]\) 上，所有的数值都加上 3.

\(index\)	0	1	2	3	4	5	6	7
\(d[i]\)	0	2+3	5+3	4+3	9+3	7	10	0
\(f[i]\)	0	2+3	3	-1	5	-2-3	3	-10

由上面的表格可以知道，这个操作在差分数组上，只影响到了差分数组区间其实位置和结束位置。

我们只需要修改一下差分数组的起始和结束位置，就可以记录这次的区间修改操作了。这样就可以把修改区间的时间复杂度 \(O(n)\) 降为 \(O(1)\)。

现在，我们如何根据差分数组 \(f\) 来推测 \(d\) 中某一个位置的值呢？

只需要求差分数组的前缀和即可。

差分数组定义

对于已知有 \(n\) 个元素的离线数列 \(d\)，我们可以建立记录它每项与前一项差值的差分数组 \(f\)，显然有：

\[ f[i]=\left\{ \begin{aligned} &d[i], &(i = 0) \\ &d[i] - d[i - 1], &(1 \leq i \lt n) \end{aligned} \right. \]

差分数组简单性质

计算数列各项的值：数组第 \(i\) 项的值是可以用差分数组的前 \(i\) 项的和计算的，即 前缀和。
计算数列每一项的前缀和：第 \(i\) 项的前缀和即为数列 \(f[i]\) 前 \(i\) 项的和。对差分数列求两次前缀和？

差分数组用途

快速处理区间加减操作：

假如现在对数列中区间 \([L, R]\) 上的数加上 \(x\)，我们通过性质 1 知道，第一个受影响的差分数组中的元素为 \(f[L]\)，即令 \(f[L]+=x\)，那么后面数列元素在计算过程中都会加上 \(x\)；最后一个受影响的差分数组中的元素为 \(f[R]\)，所以令 \(f[R+1]-=x\)，即可保证不会影响到 \(R\) 以后数列元素的计算。这样我们不必对区间内每一个数进行处理，只需要处理两个差分后的数即可；

询问区间和问题：

由性质 2 我们可以计算出数列各项的前缀和数组 \(sum\) 各项的值；那么显然，区间 \([L, R]\) 的和即为 \(ans = sum[R] - sum[L - 1]\)

差分数组应用

leetcode 1109. 航班预订统计

对于预定记录 \(booking = [l, r, inc]\)，我们需要让 \(d[l - 1]\) 增加 \(inc\)，\(d[r]\) 减少 \(inc\)。特别地，当 \(r\) 为 \(n\) 时，我们无需修改 \(d[r]\)，因为这个位置溢出了下标范围。如果求前缀和时考虑该位置，那么该位置对应的前缀和值必定为 0。

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] nums = new int[n];
        for (int[] booking : bookings) {
            nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                nums[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}