P215 不可变矩阵的部分和查询

描述#

这个题目说的是，给你一个二维整数矩阵，你要设计一个类，可以高效地查询任意子矩阵内的数字和。其中，子矩阵由它左上角坐标 (row1, col1) 和右下角坐标 (row2, col2) 所确定。

注意，你可以假设矩阵一旦给你，就不会发生改变。并且给你的左上角坐标和右下角坐标一定是合法的。另外，求子矩阵内数字和的函数会被频繁调用。

比如说，给你的矩阵 a 是：
1, 0, 2, 4
4, 2, 3, 7
3, 1, 4, 2
0, 4, 1, 4
假设子矩阵求和函数是 f，那么 f(1, 1, 2, 2) 表示的就是左上角坐标为 (1, 1)，右下角坐标为 (2, 2) 所形成的子矩阵元素和。
这个子矩阵包含的数字是：2, 3, 1, 4，因此有：
f(1, 1, 2, 2) = 2+3+1+4 = 10

相关视频：不可变数组的区间和查询

代码#

public class AlgoCasts {

  public class NumMatrixImmutable {

    private final int[][] prefixSum;

    public NumMatrixImmutable(int[][] matrix) {
      if (matrix == null || matrix.length == 0
        || matrix[0] == null || matrix[0].length == 0) {
        prefixSum = new int[1][1];
        return;
      }
      int m = matrix.length, n = matrix[0].length;
      prefixSum = new int[m+1][n+1];
      for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
          prefixSum[i][j] = prefixSum[i][j-1] + prefixSum[i-1][j]
            - prefixSum[i-1][j-1] + matrix[i-1][j-1];
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
      return prefixSum[row2+1][col2+1] - prefixSum[row2+1][col1]
        - prefixSum[row1][col2+1] + prefixSum[row1][col1];
    }

  }

}