【差分】详解二维前缀和和差分问题

1. 二维前缀和

首先来看下二维前缀和，假设现在有下面的二维数组：

现在设定 sum[i][j] 表示以 (i，j) 为右下角顶点，以（0，0）为左上角顶点的矩形的总和，比如 sum[0][0] = 1，sum[1][1] = 12 … 根据这个定义，现在给一下 sum 数组的结构。

下面就看下这个 sum 是如何计算出来的，现在先给一下公式：sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]，为了方便计算，首先我们将第一行和第一列初始化了，因为公式里面有一个 i-1 和 j-1，所以为了避免下标越界，先初始化第一行和第一列，这样后续就从 i = 1，j = 1 开始计算。

然后开始计算下面的格子：

• sum[1][1] = sum[0][1] + sum[1][0] - sum[0][0] + arr[1][1] = 12
• sum[1][2] = sum[0][2] + sum[1][1] - sum[0][1] + arr[1][2] = 21
• sum[2][1] = sum[2][0] + sum[1][1] - sum[1][0] + arr[2][1] = 27
• sum[2][2] = sum[1][2] + sum[2][1] - sum[1][1] + arr[2][2] = 45

2. 公式推导

以 sum[2][2] 为例子，下面图中蓝色部分代表 sum[2][1]，绿色部分代表 sum[1][2]，红色部分代表 sum[1][1]。

可以看到，sum[2][1] + sum[1][2] 重复添加了红色的部分，所以需要减去 sum[1][1]，最后再把 arr[2][2] 加上，就得到最终的答案了：sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]。

为了避免下标越界的判断，我们创建 sum 数组的时候让数组长度 + 1，同时改变下定义：sum[i][j] 表示从 (0，0) 到 (i-1，j-1) 这个范围的矩阵的总和。

然后就不需要先初始化好了第一行和第一列了，可以直接用 sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j] 来设置前缀和数组。

3. LeetCode 304 二维区域和检索 - 矩阵不可变

3.1 304 二维区域和检索 - 矩阵不可变

• LeetCode 304 二维区域和检索 - 矩阵不可变

class NumMatrix {int[][] sum = null;public NumMatrix(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;sum = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];}}}public int sumRegion(int row1, int col1, int row2, int col2) {return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1];}
}

3.2 LeetCode 1139 最大的以 1 为边界的正方形

• LeetCode 1139 最大的以 1 为边界的正方形

class Solution {public int largest1BorderedSquare(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] arr = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + grid[i - 1][j - 1];}}int max = 0;int len = Math.min(m, n);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int min = Math.min(len, Math.min(m - i, n - j));for (int k = 1; k <= min; k++) {// 计算四条边长, 也可以计算这个正方形的累加和 - 内部的累加和是否等于周长, 也就是(a, b, c, d) - (a + 1, b + 1, c - 1, d - 1) 的累加和// 这也比较方便if (arr[i + 1][j + k] - arr[i + 1][j] - arr[i][j + k] + arr[i][j] != k) {continue;}if (arr[i + k][j + 1] - arr[i + k][j] - arr[i][j + 1] + arr[i][j] != k) {continue;}if (arr[i + k][j + k] - arr[i + k - 1][j + k] - arr[i + k][j] + arr[i + k - 1][j] != k) {continue;}if (arr[i + k][j + k] - arr[i + k][j + k - 1] - arr[i][j + k] + arr[i][j + k - 1] != k) {continue;}max = Math.max(max, k * k);if(max == len * len){return max;}}}}return max;}
}

这里通过四次计算计算 4 条边长是不是都为 1 来判断这个正方形是不是合规的，更简单的做法是直接将这个边长的正方形的二维前缀和 - 正方形内部的前缀和，求出周长，然后再通过 k 算出周长对比就能知道正方形是不是合规，这种方式更简单。

4. 二维差分问题

首先就是二维差分，在一维差分的基础上，二维差分就是说给定一个区域 [i1，j1] -> [i2，j2] ，然后这个区域内的每个下标都加上一个数字，经过 k 次操作之后，这个二维数组会变成什么样。为什么要用二维差分，因为如果不用差分，每一次操作都需要遍历这个范围去加上数字，这样 k 次操作之后的时间复杂度就是 O(k * m * n)，但是用差分，每一次操作只需要四个步骤，最后再用前缀和处理差分数组，整个过程时间复杂度是 O(m * n)。

还是以上面的二维数组为例子，假设现在需要做 3 个操作：

• 给 [0，0] -> [1，1] 范围内的数字 + 3
• 给 [1，1] -> [2，2] 范围内的数字 - 5
• 给 [0，0] -> [2，1] 范围内的数字 + 4

最终结果如下：

现在来说下二维差分的步骤，假设要给 [x1，y1] -> [x2，y2] 这个范围的数字 + v，那么四个步骤：

• d[x1][y1] += v
• d[x2 + 1][y1] -= v
• d[x1][y2 + 1] -= v
• d[x2+1][y2+1] -= v

什么意思呢，看下面图解。

做完这几个步骤之后，将这个差分数 d 进行前缀和处理，然后再添加回原数组，就算是完成了。

5. 二维差分的原理以及差分数组计算

原理也很简单，首先要从前缀和入手，要想让一个区域的下标统一 ± v，这种情况下用前缀和是最简单的，如果考虑前缀和的情况下，就需要每一个格子对其他格子的影响，比如下面的例子。

当我们要给 [0，0] -> [1，1] 范围内的数字 + 3 时，首先就是设置 d[0][0] + 3，考虑到 d[0][0] 这个位置会影响到整个二维数组的前缀和，也就是这里加了 3 之后计算前缀和时其他格子全部都要 + 3，而我们的目标只是 [0，0] -> [1，1] 这个范围，因此我们需要通过：

• d[2][0] - 3 消除 [2，0] -> [2，2] 的影响
• d[0][2] - 3 消除 [0，2] -> [2，2] 的影响

但是消除影响之后明显能发现，右下角以 [2，2] 为右上角的区域重复消除了，所以需要在 d[2][2] + 3 来抵消掉重复消除，最终就是这四个步骤了。

• d[x1][y1] += v
• d[x2 + 1][y1] -= v
• d[x1][y2 + 1] -= v
• d[x2+1][y2+1] -= v

经过这几个步骤，再求前缀和就能得到 k 次操作的影响，然后添加回原数组就行了。大家也可以注意下，这里我们算影响范围算前缀和的时候没有让 i，j 都 + 1，也就是没有像第 3 小节那个题目那样计算前缀和，因为 d 数组本身为了不越界需要 + 1 处理，所以为了方便计算，前缀和也没有 + 1，只是在原来的数组上进行前缀和，也就是定义 sum[i][j] 为以 i，j 为右下角的区域的前缀和。

如果不想要添加回原数组，可以直接通过原始数组求出差分数组来计算，差分数组计算公式是：d[i][j] = arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1]，是通过原始数组计算出来的。计算出差分数组之后可以通过前缀和直接算出原始数组，这样在解题的时候就可以把最后一步添加回原数组去掉了，就比如下面的计算，只是下面题目用的都是不计算差分数组的方式，所以注意下。

6. 题目

题目来自左神的题单，算法讲解048【必备】二维前缀和、二维差分、离散化技巧

6.1 牛客二维差分

• 【模板】二维差分

import java.util.*;
import java.lang.*;public class Main {static int n = 0, m = 0, q = 0;static long[][] arr = null;static long[][] d = null;public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 casen = in.nextInt();m = in.nextInt();q = in.nextInt();arr = new long[n][m];d = new long[n + 1][m + 1];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {arr[i][j] = in.nextInt();}}for (int i = 0; i < q; i++) {int x1 = in.nextInt() - 1;int y1 = in.nextInt() - 1;int x2 = in.nextInt() - 1;int y2 = in.nextInt() - 1;int v = in.nextInt();d[x1][y1] += v;d[x1][y2 + 1] -= v;d[x2 + 1][y1] -= v;d[x2 + 1][y2 + 1] += v;}}// 对 d 求前缀和for(int i = 0; i <= n; i++){for(int j = 0; j <= m; j++){d[i][j] += getNum(i, j - 1) + getNum(i - 1, j) - getNum(i - 1, j - 1);}}// 加回原数组for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){arr[i][j] += d[i][j];System.out.print(arr[i][j] + " ");}System.out.println();}}public static long getNum(int x, int y) {if (x < 0 || y < 0) {return 0;} else {return d[x][y];}}}

6.2 LeetCode 2132. 用邮票贴满网格图

• LeetCode 2132. 用邮票贴满网格图

class Solution {public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {int m = grid.length;int n = grid[0].length;int[][] preSum = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + grid[i - 1][j - 1];}}int[][] arr = new int[m + 2][n + 2];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0 && m - i >= stampHeight && n - j >= stampWidth) {// 如果 stampHeight * stampWidth 区域内都是 0 就说明可以贴if (preSum[i + stampHeight][j + stampWidth] - preSum[i + stampHeight][j] - preSum[i][j + stampWidth] + preSum[i][j] == 0) {// arr 数组 + 2 是因为上下左右都用 0 包围起来了// 差分数组的处理, 区域内左上角 + 1, 区域外(右边 - 1, 下边 - 1, 右下角 + 1)arr[i + 1][j + 1] += 1;arr[i + stampHeight + 1][j + 1] -= 1;arr[i + 1][j + stampWidth + 1] -= 1;arr[i + stampHeight + 1][j + stampWidth + 1] += 1;}}}}// 处理差分数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 差分数组每个格子 左 + 上 - 左上 + 自己arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + arr[i][j];}}// 将差分数组和原数组做对比for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (grid[i - 1][j - 1] == 0 && arr[i][j] == 0) {return false;}}}return true;}}

可以看到这里用的二维前缀和定义做了 + 1处理，也就是 int[][] preSum = new int[m + 1][n + 1]，所以接下来求 d 差分数组的时候为了避免越界也进行了 + 2 处理，但是这样写起来就比较乱，所以涉及到差分的前缀和还是直接根据 6.1 的方式来写比较好。

6.3 LeetCode LCP74 最前祝福立场

• LeetCode LCP74 最前祝福立场

class Solution {
// 离散化: (x, y, r) -> 左边界, 右边界 = (2x - r, 2x + r), 上边界, 下边界 = (2y + r, 2y - r)public int fieldOfGreatestBlessing(int[][] forceField) {List<Long> listX = new ArrayList<>();List<Long> listY = new ArrayList<>();for (int[] arr : forceField) {long x = arr[0] * 1L;long y = arr[1] * 1L;long r = arr[2] * 1L;listX.add(2 * x - r);listX.add(2 * x + r);listY.add(2 * y - r);listY.add(2 * y + r);}Collections.sort(listX);Collections.sort(listY);listX = listX.stream().distinct().collect(Collectors.toList());listY = listY.stream().distinct().collect(Collectors.toList());int n = listX.size();int m = listY.size();int[][] as = new int[m + 2][n + 2];for (int[] arr : forceField) {int x = arr[0];int y = arr[1];int r = arr[2];int lx = search(2L * x - r, listX);int rx = search(2L * x + r, listX);int dy = search(2L * y - r, listY);int uy = search(2L * y + r, listY);as[dy + 1][lx + 1] += 1;as[uy + 2][lx + 1] -= 1;as[dy + 1][rx + 2] -= 1;as[uy + 2][rx + 2] += 1;}int ans = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {as[i][j] += as[i - 1][j] + as[i][j - 1] - as[i - 1][j - 1];ans = Math.max(ans, as[i][j]);}}return ans;}public int search(long target, List<Long> list) {int left = 0, right = list.size() - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (list.get(mid) > target) {right = mid - 1;} else if (list.get(mid) < target) {left = mid + 1;} else {return mid;}}return -1;}
}

如有错误，欢迎指出！！！