差分数组.md

何言 2021年08月11日 95次浏览

差分数组与前缀和数组

什么是前缀和数组

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

对于原数组 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 和两个整数 leftright 。每个 ranges[i] = [starti, endi] 表示一个从 startiendi 的 闭区间 。

    如果闭区间 [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;
    }
}