【CSP考点回顾】差分数组

差分数组是高效处理数组区间修改问题的方法，适用于对原始数组的连续区间频繁地进行增加或减少操作的情形。

• 例如，输入一个数组 $nums$，要求给区间 $nums[\mathrm{2...6}]$ 全部加1，再给 $nums[3…9] $ 全部减3，再给 $nums[\mathrm{0...4}]$ 全部加2，再给……问：最后 $nums$ 数组中各元素的值是什么？
• 【常规思路】：使用 for 循环给给区间 $nums[i..j]$ 加上 $val$，该思路的时间复杂度是 $O(N)$。由于这个场景下对 $nums$ 的修改非常频繁，所以效率会很低。
• 【差分数组】：类似前缀和构造的 $prefix$ 数组，对 $nums$ 数组构造 $diff$ 差分数组，$diff[i]=nums[i]-nums[i-1]$。

1.差分数组

差分数组，记为 $diff$，是根据原数组 $nums$ 构建的一个新数组，其中 $diff[i]$ 表示 $nums[i]$ 与 $nums[i-1]$ 的差值。对于数组的第一个元素，$diff[0]=nums[0]$，因为没有前一个元素与之比较。差分数组的主要优势在于它可以快速、高效地对原始数组的任意连续区间进行修改。

2.差分数组的构造

构建差分数组 $diff$，遵循以下步骤：

1. 初始化 $diff$ 数组，使其长度与原数组 $nums$ 相同。
2. 设定 $diff[0]=nums[0]$。
3. 对于 $diff$ 数组中的其他元素，执行 $diff[i]=nums[i]-nums[i-1]$。

int[] diff = new int[nums.length];
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}
1
2
3
4
5

3.使用差分数组进行区间修改

当需要对原数组 $nums$ 的连续区间 $[i..j]$ 进行修改，即对该区间内所有元素增加或减少某个值 $val$ 时，我们只需要更新差分数组 $diff$：

• 令 $diff[i]+=val$。
• 如果 $j+1<nums.length$，则 $diff[j+1]-=val$。

这样，我们就在 $O(1)$ 的时间复杂度内完成了区间的修改，而不需要遍历整个区间。原理很简单，回想 $diff$ 数组反推 $nums$ 数组的过程, $diff[i]+=val$ 意味着给 $nums[i..]$ 所有的元素都加了 $val$，然后 $diff[j+1]-=val$ 又意味着对于 $nums[j+\mathrm{1..}]$ 所有元素再减 $val$。综合起来，就是对 $nums[i..j]$ 中的所有元素都加 $val$ 了

• 如，对 $[\mathrm{2..4}]$ 全部+8，即 $diff[2]+=8$， $diff[5]-=8$

4.从差分数组还原原数组

修改完差分数组后，可以通过以下步骤还原修改后的原数组 $nums$：

1. 初始化结果数组 $res$，使其长度与 $diff$ 相同。
2. 设定 $res[0]=diff[0]$。
3. 对于 $res$ 数组中的其他元素，执行 $res[i]=res[i-1]+diff[i]$。

int[] res = new int[diff.length];
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}
1
2
3
4
5

---

本文部分内容参考自：【labuladong】前缀和/差分数组技巧精讲