二维前缀和模板：

一维前缀和: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];

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

也就是数说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]; } } |