【差分数组】区间加法「差分数组基础」

题目

370. 区间加法

---

假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k​​​​​​​ 个更新的操作。

其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex … endIndex]（包括 startIndex 和 endIndex）增加 inc。

请你返回 k 次操作后的数组。

示例:

输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
输出: [-2,0,3,5,3]

解释:

初始状态:
[0,0,0,0,0]

进行了操作 [1,3,2] 后的状态:
[0,2,2,2,0]

进行了操作 [2,4,3] 后的状态:
[0,2,5,5,3]

进行了操作 [0,2,-2] 后的状态:
[-2,0,3,5,3]

解题

方法一：差分数组

思路

差分数组裸题。

差分数组

差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减。

例如如果要对 ori 数组构造一个 diffs 差分数组，diffs[i] 就是 ori[i] 与 ori[i-1] 之差，在差分数组 diffs 中我们只需关注变化的点，其他的点不用关心。

所以当我们希望对原数组的某一个区间 [l, r] 整体增加 delta 时，差分数组 diffs 对应的变化是：diffs[l] += delta，diffs[r+1] -= delta，并且这种操作是可以叠加的。

举个例子：对 nums = [1, 2, 3, 4, 5, 6] 中所有数全部加 1，再把从 nums[1] 到 nums[3] 之间(包括)所有数加 3 ，此时的差分数组 diffs = [1, 3, 0, 0, -3, 0, -1]，然后我们初始化变化量 diff = 0，开始遍历 nums：

• i = 0, diff += diffs[0] => diff = 1, nums[i] += diff => nums[i] = 2
• i = 1, diff += diffs[1] => diff = 4, nums[i] += diff => nums[i] = 6
• i = 2, diff += diffs[2] => diff = 4, nums[i] += diff => nums[i] = 7
• i = 3, diff += diffs[3] => diff = 4, nums[i] += diff => nums[i] = 8
• i = 4, diff += diffs[4] => diff = 1, nums[i] += diff => nums[i] = 6
• i = 5, diff += diffs[5] => diff = 1, nums[i] += diff => nums[i] = 7

这样下来，无论区间是交叉还是嵌套，差分数组都可以高效处理。

参考：

• 差分攻略
• Leetcode刷题笔记——差分数组

代码

class Solution {
    public int[] getModifiedArray(int length, int[][] updates) {
        int[] diffs = new int[length + 1];
        for (int[] update : updates) {
            diffs[update[0]] += update[2];
            diffs[update[1] + 1] -= update[2];
        }
        int[] ans = new int[length];
        for (int i = 0, num = 0; i < length; ++i) ans[i] = num += diffs[i];
        return ans;
    }
}