二维前缀和与差分深度解析

一、二维前缀和

1.1 基本概念

二维前缀和（也称为二维累加和）是一个二维数组，其中每个元素sum[i][j]表示原数组中从左上角(0,0)到右下角(i,j)所构成的矩形区域内所有元素的和。通过预处理计算出二维前缀和数组后，可以在O(1)时间内查询任意子矩形区域的和。

1.2 算法原理

1.2.1 前缀和数组的构造

构造二维前缀和数组sum[i][j]的递推公式如下：

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i][j]

其中，matrix[i][j]表示原数组中第i行第j列的元素。

这个公式的推导基于容斥原理：为了计算从(0,0)到(i,j)的矩形区域和，我们可以将其分解为三个部分：

• 上方矩形区域(0,0)到(i-1,j)的和sum[i-1][j]
• 左方矩形区域(0,0)到(i,j-1)的和sum[i][j-1]
• 左上角重叠区域(0,0)到(i-1,j-1)的和sum[i-1][j-1]（由于被重复计算了两次，需要减去一次）
• 当前元素matrix[i][j]
  

1.2.2 子矩形区域和的查询

利用前缀和数组，可以在O(1)时间内查询任意子矩形区域(x1,y1)到(x2,y2)的和，公式如下：

sum = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]

这里的(x1,y1)是子矩形的左上角坐标，(x2,y2)是右下角坐标。

1.3 Java实现

下面是构造二维前缀和数组并查询子矩形区域和的Java代码实现：

public class TwoDimensionalPrefixSum {private int[][] sum; // 二维前缀和数组// 构造函数，预处理前缀和数组public TwoDimensionalPrefixSum(int[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return;}int m = matrix.length;int n = matrix[0].length;sum = new int[m + 1][n + 1]; // 为了方便处理边界，前缀和数组行和列各增加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];}}}// 查询子矩形区域(x1,y1)到(x2,y2)的和// 注意：这里的坐标是原矩阵的坐标，从0开始public int query(int x1, int y1, int x2, int y2) {// 转换为前缀和数组的坐标（前缀和数组从1开始）x1++; y1++; x2++; y2++;return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];}// 示例用法public static void main(String[] args) {int[][] matrix = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}};TwoDimensionalPrefixSum ps = new TwoDimensionalPrefixSum(matrix);// 查询子矩形(0,0)到(1,2)的和（对应原矩阵的左上角2x3区域）int sum = ps.query(0, 0, 1, 2);System.out.println("子矩形区域的和为: " + sum); // 输出: 1+2+3+5+6+7=24}
}

1.4 复杂度分析

• 预处理时间复杂度：O(mn)，其中m和n分别是原矩阵的行数和列数。
• 单次查询时间复杂度：O(1)。
• 空间复杂度：O(mn)，主要用于存储前缀和数组。

1.5 应用场景

• 频繁查询二维数组中子矩形区域的和：例如在图像处理中计算像素区域的亮度总和。
• 二维区域统计问题：如统计矩阵中满足特定条件的子矩形数目。

二、二维差分

2.1 基本概念

二维差分是二维前缀和的逆运算，用于高效处理二维数组的区间更新问题。通过维护一个差分数组，可以在O(1)时间内完成对子矩形区域的批量更新操作，最后通过差分还原得到更新后的原数组。

2.2 算法原理

2.2.1 差分数组的构造

给定原数组matrix，其差分数组diff[i][j]定义为：

diff[i][j] = matrix[i][j] - matrix[i-1][j] - matrix[i][j-1] + matrix[i-1][j-1]

其中，当i=0或j=0时，matrix[i-1][j]或matrix[i][j-1]视为0。

2.2.2 子矩形区域更新

若要将原矩阵中从(x1,y1)到(x2,y2)的子矩形区域内所有元素加上值val，只需在差分数组上进行如下操作：

diff[x1][y1] += val;
diff[x1][y2+1] -= val;
diff[x2+1][y1] -= val;
diff[x2+1][y2+1] += val;

2.2.3 还原原数组

更新完差分数组后，通过前缀和运算还原得到更新后的原数组：

matrix[i][j] = matrix[i-1][j] + matrix[i][j-1] - matrix[i-1][j-1] + diff[i][j]

2.3 Java实现

下面是二维差分的Java实现，包括差分数组的构造、区域更新和原数组的还原：

public class TwoDimensionalDifference {private int[][] diff; // 二维差分数组private int m, n;     // 原矩阵的行数和列数// 构造函数，初始化差分数组public TwoDimensionalDifference(int[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return;}m = matrix.length;n = matrix[0].length;diff = new int[m + 2][n + 2]; // 为了方便处理边界，差分数组行列各增加2// 构造差分数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {diff[i][j] = matrix[i - 1][j - 1];if (i > 1) diff[i][j] -= matrix[i - 2][j - 1];if (j > 1) diff[i][j] -= matrix[i - 1][j - 2];if (i > 1 && j > 1) diff[i][j] += matrix[i - 2][j - 2];}}}// 对子矩形区域(x1,y1)到(x2,y2)内的所有元素加上val// 注意：这里的坐标是原矩阵的坐标，从0开始public void update(int x1, int y1, int x2, int y2, int val) {// 转换为差分数组的坐标（差分数组从1开始）x1++; y1++; x2++; y2++;diff[x1][y1] += val;diff[x1][y2 + 1] -= val;diff[x2 + 1][y1] -= val;diff[x2 + 1][y2 + 1] += val;}// 还原得到更新后的原数组public int[][] getResult() {int[][] result = new int[m][n];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {result[i - 1][j - 1] = diff[i][j];if (i > 1) result[i - 1][j - 1] += result[i - 2][j - 1];if (j > 1) result[i - 1][j - 1] += result[i - 1][j - 2];if (i > 1 && j > 1) result[i - 1][j - 1] -= result[i - 2][j - 2];}}return result;}// 示例用法public static void main(String[] args) {int[][] matrix = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}};TwoDimensionalDifference td = new TwoDimensionalDifference(matrix);// 将子矩形(0,0)到(1,2)的所有元素加5td.update(0, 0, 1, 2, 5);// 获取更新后的数组int[][] result = td.getResult();// 输出更新后的数组for (int[] row : result) {for (int num : row) {System.out.print(num + "\t");}System.out.println();}}
}

2.4 复杂度分析

• 构造差分数组时间复杂度：O(mn)。
• 单次区域更新时间复杂度：O(1)。
• 还原原数组时间复杂度：O(mn)。
• 空间复杂度：O(mn)。

2.5 应用场景

• 频繁对子矩形区域进行批量更新：如游戏地图中的区域状态更新。
• 二维数组的区间染色问题：如在画布上对特定区域进行颜色填充。

三、典型例题与应用

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

题目描述：给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为(row1, col1)，右下角为(row2, col2)。

解题思路：使用二维前缀和预处理矩阵，实现O(1)时间的查询。

Java代码：

class NumMatrix {private int[][] sum;public NumMatrix(int[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return;}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) {row1++; col1++; row2++; col2++;return sum[row2][col2] - sum[row1 - 1][col2] - sum[row2][col1 - 1] + sum[row1 - 1][col1 - 1];}
}

3.2 子矩阵查询

题目描述：给定一个n×m的矩阵，初始值均为0，接下来有q个操作，每个操作将一个子矩阵的所有元素加1，最后输出整个矩阵。

解题思路：使用二维差分处理区间更新，最后还原得到结果矩阵。

Java代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int q = scanner.nextInt();int[][] diff = new int[n + 2][m + 2];// 处理q次操作for (int i = 0; i < q; i++) {int x1 = scanner.nextInt();int y1 = scanner.nextInt();int x2 = scanner.nextInt();int y2 = scanner.nextInt();// 差分更新diff[x1][y1]++;diff[x1][y2 + 1]--;diff[x2 + 1][y1]--;diff[x2 + 1][y2 + 1]++;}// 还原结果矩阵int[][] res = new int[n + 1][m + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {res[i][j] = diff[i][j] + res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1];}}// 输出结果矩阵for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {System.out.print(res[i][j] + " ");}System.out.println();}}
}

四、总结与扩展

4.1 核心总结

• 二维前缀和：通过预处理将二维数组的区间查询时间复杂度优化到O(1)，适用于频繁查询的场景。
• 二维差分：通过维护差分数组将二维数组的区间更新时间复杂度优化到O(1)，适用于频繁更新的场景。

4.2 扩展与变形

• 高维前缀和与差分：将二维前缀和与差分的思想扩展到三维或更高维的数组。
• 动态二维前缀和：结合线段树或树状数组等数据结构，支持动态更新和查询。

4.3 注意事项

• 处理边界情况时，通常将前缀和数组和差分数组的行列各增加1或2，以避免复杂的边界判断。
• 理解前缀和与差分的数学原理是灵活运用的关键。

That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～