每日算法 二维区域和检索 - 矩阵不可变

例题：LCR 013. 二维区域和检索 - 矩阵不可变

题目描述：

给定一个二维矩阵 matrix，以下类型的多个请求：

• 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

实现 NumMatrix 类：

• NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
• int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

代码：

class NumMatrix {
    private int[][] preSum;
    
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        if (m == 0 || n == 0) return;
        preSum = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i][j] = preSum[i][j-1] + preSum[i-1][j] - preSum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2+1][col2+1] - preSum[row1][col2+1] - preSum[row2+1][col1] + preSum[row1][col1]; 
    }
}

思路：使用前缀和思想。通过用m和n获取矩阵的行和列，再定义前缀和矩阵preSum，因为前缀和默认[0][0],[0][1],[1][0]的时候都为0，且前缀和矩阵特性的原因，for循环里面套的是int i = 1; i <= m;这样子从1开始的，i 能= m是因为前缀和要比原matrix矩阵数组大一圈。

所以前缀矩阵很容易就能得出preSum[i][j] = preSum[i][j-1] + preSum[i-1][j] - preSum[i-1][j-1] + matrix[i-1][j-1];。

这一条代码的思想来源于下图：

要想得到D区域，我们可以用Sum(D) = Sum(ABCD) - Sum(AC) - Sum(AB) + Sum(A) ，我们现在是想要填充满前缀和矩阵preSum，preSum[i][j]就等于Sum(ABCD)，Sum(AC)就等于preSum[i][j-1]，Sum(AB)就等于preSum[i-1][j]，Sum(A)就等于matrix[i-1][j-1] 。

所以这条式子变换一下，Sum(ABCD) = Sum(D) + Sum(AC) + Sum(AB) - Sum(A) 就等于 preSum[i][j] = preSum[i][j-1] + preSum[i-1][j] - preSum[i-1][j-1] + matrix[i-1][j-1]。

这个代码内的过程其实是拆解细分的，不是像做数学一样直接知道A\B\C\D这四块区域各自的区域和再直接去计算想要的区域和。

数学是直接的块与块之间的计算，而代码的计算是边算区域的总和边做计算得出想要的结果，也就是说在计算区域和的过程中，就已经在相互计算直接得出来想要的结果。代码虽然自始至终都是单个数值之间的计算，但从结果的总体角度来看，这些单个数字之间的计算各自拆分并累加起来就是块与块之间的计算。