【进阶算法】差分

差分是一种类似于前缀和的编码技巧，可以快速实现对数组某个区间的所有元素增加或减少一个值。

一、差分数组

示例：数组 arr = [8，1，3，-2，5，0，-3，6]，输入 m 个操作，每个操作输入 (L , R, val)，表示对数组的 [L, R] 区间中每个元素增加 val，要求输出最后的 arr 数组。

比如，第 1 次操作，输入 (0 , 2, 1)；第 2 次操作，输入 (2 , 5, 3)；第 3 次操作，输入 (0 , 6, -1)。最后，arr = [8，1，6，0，7，2，-4，6]。

常规的思路很容易想到，每次遍历区间 [L, R]，给每个元素加上 val，但是每次遍历数组，时间复杂度比较高。可以使用差分数组提高处理效率。

差分思想：

定义一个差分数组 diff[arr.len]，其中 diff[0] = arr[0]，diff[i] = arr[i] - arr[i - 1]，表示原数组中每个元素与前一个元素的差值。

/**
 * 构造差分数组
 *
 * @param arr 原数组
 * @return 差分数组
 */
private int[] diff(int[] arr) {
    int len = arr.length;
    int[] diff = new int[len];
    diff[0] = arr[0];
    for (int i = 1; i < len; i++) {
        diff[i] = arr[i] - arr[i - 1];
    }
    return diff;
}

差分数组的前缀和就是原数组。

/**
 * 根据差分数组反推原数组
 *
 * @param diff 差分数组
 * @return 原数组
 */
private int[] original(int[] diff) {
    int len = diff.length;
    int[] arr = new int[len];
    arr[0] = diff[0];
    for (int i = 1; i < len; i++) {
        arr[i] = arr[i - 1] + diff[i];
    }
    return arr;
}

通过差分数组可以快速对原数组某个区间的所有元素增加或减少一个值，比如，给原数组 [L, R] 区间每个元素增加 val，只需要 diff[L] += val, diff[R + 1] -= val 即可。根据差分数组反推原数组的过程可知，diff[L] += val 代表给原数组 L 之后的所有元素增加了 val，diff[R + 1] -= val 代表给原数组 R + 1 之后的所有元素都减少了 val，所以最终是给 [L, R] 区间中的每个元素增加了 val。

二、代码实现

// 原数组
int[] arr = {8, 1, 3, -2, 5, 0, -3, 6};
// 差分数组
int[] diff = diff(arr);

/**
 * 构造差分数组
 *
 * @param arr 原数组
 * @return 差分数组
 */
private int[] diff(int[] arr) {
    int len = arr.length;
    int[] diff = new int[len];
    diff[0] = arr[0];
    for (int i = 1; i < len; i++) {
        diff[i] = arr[i] - arr[i - 1];
    }
    return diff;
}

/**
 * 给原数组 [left, right] 区间每个元素增加 val
 *
 * @param left  区间左边界
 * @param right 区间右边界
 * @param val   增加的数值
 */
public void increment(int left, int right, int val) {
    diff[left] += val;
    if (right + 1 < diff.length) {
        diff[right + 1] -= val;
    }
}

/**
 * 根据差分数组计算修改后的原数组
 *
 * @param diff 差分数组
 * @return 修改后的原数组
 */
private int[] original(int[] diff) {
    int len = diff.length;
    int[] arr = new int[len];
    arr[0] = diff[0];
    for (int i = 1; i < len; i++) {
        arr[i] = arr[i - 1] + diff[i];
    }
    return arr;
}

三、适用场景

差分数组的适用场景：

  频繁对原始数组的某个区间所有元素进行增减操作。

四、练习题目

LeetCode 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]

LeetCode 1109. 航班预订统计

LeetCode 1094. 拼车