二维前缀和模板:

一维前缀和:sum[i,j]=sum[j+1]-sum[i]

将sum[i][j]看成是以 matrix[0][0] 为左上角顶点, matrix[i-1][j-1] 为右下角顶点的矩阵内所有元素的和

初始化sum矩阵:sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + matrix[i][j];

p21

区块求和: sumRegion(r1, c1, r2, c2)=sum[r2 + 1, c2 + 1] - sum[r1, c2 + 1] - sum[r2 + 1, c1] + sum[r1, c1]

p22

也就是数说sum[i][j]是比matrix超前一位

代码如下:

class NumMatrix {

int[][] sum;

public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
sum = new int[m + 1][n + 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] - sum[i][j] + matrix[i][j];
}
}
}

// 求以(r1,c1)为左上角,(r2,c2)为右下角的区块和
public int sumRegion(int r1, int c1, int r2, int c2) {
return sum[r2 + 1][c2 + 1] - sum[r1][c2 + 1] - sum[r2 + 1][c1] + sum[r1][c1];
}

}