二维区域和检索-矩阵不可变
  该题目和一维不同的在于多了一列，那么我们应该最开始的想法就是压缩成一维不就行了，即对每行进行行求和，然后计算是则遍历行计算即可，但是我们会发现就是在计算中还是有遍历，因为不是特别好，所以该改进就是不压缩，而是合理利用行列特性，找行列关系如同一维找行关系一样，此时每一点就为以此为右下角的矩阵求和的值。第一个不展示，这里只展示第二种算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class NumMatrix {
    public  int[][] mat;
    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        mat = new int[m][n];
        for(int i = 0;i < m ;i++){
            for(int j = 0; j<n;j++){
                if(i==0&&j==0){
                    mat[i][j] = matrix[i][j];
                }else if(i==0){
                     mat[i][j] = matrix[i][j]+mat[i][j-1];
                }else if(j==0){
                    mat[i][j] = matrix[i][j]+mat[i-1][j];
                }else{
                    mat[i][j] = matrix[i][j]+mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1];
                }
            }
        }

    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(col1 == 0&&row1==0){
            return mat[row2][col2];
        }else if(row1==0){
            return mat[row2][col2] - mat[row2][col1-1];
        }else if(col1==0){
            return mat[row2][col2] - mat[row1-1][col2];
        }else{
            return mat[row2][col2] - mat[row1-1][col2] - mat[row2][col1-1] + mat[row1-1][col1-1];
        }
    }
}