差分数组技巧

1109. 航班预订统计

1094. 拼车

在介绍差分数组之前，先回顾了一下「前缀和数组」详情可见 前缀和数组

前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和

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

使用场景：对于一个数组nums[]

• 要求一：对num[2...4]全部 + 1
• 要求二：对num[1...3]全部 - 3
• 要求三：对num[0...4]全部 + 9

看到上述情景，首先想到的肯定是遍历（bao li）法。直接对数组循环 3 遍，每次在规定的区间上按要求进行操作，此时时间复杂度O(3n)

但是当这样的操作变得频繁后，时间复杂度也呈线性递增

所以针对这种场景，出现了「差分数组」的概念，举个简单的例子

diff[]和nums[]的关系：diff[i] = nums[i] - nums[i - 1]，diff[0]除外

问题一：这样处理的好处是什么呢？？？？？

当我们需要对nums[]进行上述三个要求时，不需要一次一次的遍历整个数组了，而只需要对diff[]进行一次O(1)的操作即可

• 要求一：diff[2] += 1;
• 要求二：diff[1] += (-3); diff[3 + 1] -= (-3);
• 要求三：diff[0] += 9;

总结：对于改变区间[i, j]的值，只需要进行如下操作diff[i] += val; diff[j + 1] -= val

注：当j + 1 >= diff.length时，不需要进行diff[j + 1] -= val操作

问题二：怎么通过diff[]得到更新后的数组呢？？？？？

// 复原操作
int[] res = new int[n];
// 下标为 0 的元素相等
res[0] = diff[0];
for (int i = 1; i < n; i++) {
    res[i] = diff[i] + res[i - 1];
}

问题三：diff[]原理

当我们需要对区间[i, j]进行+ val操作时，我们对diff[i] += val; diff[j + 1] -= val;

在复原操作时，当我们求res[i]时，res[i - 1]没有变，而diff[i]增加了 3，所以res[i]增加 3

当我们求res[i + 1]时，res[i]增加了 3，而diff[i + 1]没有变，故res[i + 1] = diff[i + 1] + res[i]增加 3。即：虽然diff[i + 1]没有变，但是res[i]对后面的res[i + 1]有一个累积作用

当我们求res[j + 1]时，res[j]增加了 3，而diff[j + 1]减少了 3，故res[j + 1] = diff[j + 1] + res[j]增加没有变。即：我们在j + 1的时候，把上述的累积作用去除了，所以j + 1后面的元素不受影响

完整模版

​x
public class Difference {

    /**
     * 差分数组
     */
    private final int[] diff;

    /**
     * 初始化差分数组
     * @param nums nums
     */
    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /**
     * 对区间 [i, j] 增加 val（val 可为负数）
     * @param i i
     * @param j j
     * @param val val
     */
    public void increment(int i, int j, int val) {
        diff[i] += val;
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    /**
     * 复原操作
     * @return res
     */
    public int[] result() {
        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];
        }
        return res;
    }
}