差分数组.md

差分数组与前缀和数组

什么是前缀和数组

前缀和数组是一个辅助数组，下面给出定义：

对于原数组 nums[i] ，
其前缀和数组 sums[i] = (nums[0] + nums[1] + … + nums[i])

前缀和数组下标为 i 的数字表示原数组从 0 到 i 的数的和。

前缀和数组的性质

前缀和数组主要用于频繁求区间和 ：

定义 nums[i, j] = (nums[i] + nums[i+1] + … + nums[j-1] + nums[j])
则可得 nums[i, j] = sums[j] - sums[i-1] , 特别的 nums[0, j] = sums[j]

可以看到，求区间和的操作变为了 O(1) ，这就是前缀和数组最大的作用。

什么是差分数组

差分数组也是一个辅助数组，下面给出定义：

对于原数组 nums[i]
其差分数组 diff[i] = nums[i] - nums[i-1] 特别的 diff[0] = nums[0]

可以看到差分数组其实是求前缀和数组的逆操作，当我们求 diff 的前缀和数组时，我们会得到原数组 nums

差分数组的性质

差分数组主要用于子区间的频繁加减

这里为了方便，直接给出具体数值：

假设有数组 nums[i] = {1, 5, 6, 8, 0}
其差分数组 diff[i] = {1, 4, 1, 2, -8}

我们需要给 数组 nums[i] 中区间 [1, 3] (下标) 中的所有数字都加 3

操作后原数组 nums[i] = {1, 8, 9, 11, 0}
操作后差分数组 diff[i] = {1, 7, 1, 2, -11}

操作前差分数组 diff[i] = {1, 4, 1, 2, -8}

可以看到对于差分数组，这操作相当于 diff[1] += 3 , diff[3+1] -= 3

也就是对于原数组的区间进行一样的修改，在差分数组中只需要对端点值进行对应修改，这就是差分数组的意义。

差分数组例题

因为前缀和数组相对简单，这里给出差分数组的例题：

• 1893. 检查是否区域内所有整数都被覆盖

• 给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。

  如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false 。

  已知区间 ranges[i] = [starti, endi] ，如果整数 x 满足 starti <= x <= endi ，那么我们称整数 x 被覆盖了。

• 1 <= ranges.length <= 50
• 1 <= starti <= endi <= 50
• 1 <= left <= right <= 50

对于区间 [2, 3] ， 我们可以表示为 {0, 0, 1 ,1 ,0}

对于区间 [1, 3] ， 我们可以表示为 {0, 1, 1, 1, 0}

将区间进行合并，得到 {0, 1, 2, 2, 0}

此时判断题目给出的 left 到 right 的下标，如果中间某个整数的数字小于或等于 0 ，则返回 false

这里可以用差分数组来实现：

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        int[] diff = new int[52];   // 差分数组
        for (int[] range : ranges) {
            ++diff[range[0]];
            --diff[range[1] + 1];
        }
        // 前缀和
        int curr = 0;
        for (int i = 1; i <= 50; ++i) {
            curr += diff[i];
            if (i >= left && i <= right && curr <= 0) {
                return false;
            }
        }
        return true;
    }
}