二维前缀和模板：

一维前缀和: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超前一位的

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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];
    }
    
}