算法33，矩阵区域求和，二维前缀和

一、预处理：求 dp[i][j]

定义 dp[i][j] = 从左上角 (1,1) 到 (i,j) 这个矩形内所有元素的和。

递推时，当前格 (i,j) 的矩形由四块拼成：

dp[i][j]=dp[i−1][j]+dp[i][j−1]−dp[i−1][j−1]+a[i][j]

即：上面整块 A + 左边整块 B − 重复算了一次的左上角 C + 自己。这就是你笔记里 A+B−C+D 的那一笔（D 是当前格）。

二、查询：求任意子矩阵的和

要求左上角 (x1,y1)、右下角 (x2,y2) 的区域和：

sum=dp[x2​][y2​]−dp[x1​−1][y2​]−dp[x2​][y1​−1]+dp[x1​−1][y1​−1]

口诀：大矩形 − 上面 − 左边 + 被多减了一次的左上角。

这样单次查询从 O(面积) 降到 O(1)。

三、用手里的 3×3 矩阵推一遍

以矩阵为例：

1 2 3
4 5 6
7 8 9

对应的 dp（1-indexed）：

j=1

j=2

j=3

验算右下角 2×2（(2,2)~(3,3)，实际是 5+6+8+9=28）：

45−dp[1][3]−dp[3][1]+dp[1][1]=45−6−12+1=28✓

四、边界处理（笔记里的 max / min）

题目常给"以 (x,y) 为中心、半径为 r 的矩形"（如 LeetCode 1314），坐标会越界，必须先 clamp​ 再查询：

int x1 = Math.max(0, i – r), x2 = Math.min(m – 1, i + r);
int y1 = Math.max(0, j – r), y2 = Math.min(n – 1, j + r);

这是 0-indexed 写法；若 dp 用 1-indexed，则 clamp 到 [1, m] / [1, n]，两边别混用。

五、Java 代码

① 预处理 + 查询（LeetCode 304）

class NumMatrix {
private int[][] dp; // dp[i+1][j+1] 对应前 i+1 行、j+1 列

public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
dp = new int[m + 1][n + 1]; // 多开一行一列当哨兵
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1]
– dp[i-1][j-1] + matrix[i-1][j-1];
}

// 返回 0-indexed 的 [row1,row2] × [col1,col2] 区域和
public int sumRegion(int row1, int col1, int row2, int col2) {
return dp[row2+1][col2+1]
– dp[row1][col2+1]
– dp[row2+1][col1]
+ dp[row1][col1];
}
}

② 矩阵区域和（LeetCode 1314，含边界 clamp）

public int[][] matrixBlockSum(int[][] mat, int r) {
int m = mat.length, n = mat[0].length;
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1]
– dp[i-1][j-1] + mat[i-1][j-1];

int[][] ans = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x1 = Math.max(0, i – r), x2 = Math.min(m – 1, i + r);
int y1 = Math.max(0, j – r), y2 = Math.min(n – 1, j + r);
ans[i][j] = dp[x2+1][y2+1] – dp[x1][y2+1]
– dp[x2+1][y1] + dp[x1][y1];
}
}
return ans;
}

复杂度：预处理 O(mn)、空间 O(mn)，每次查询 O(1)。