差分&&前缀和

前缀和

区间和 记住一个n+1(方便操作) i-1(因为是和相减，所以不能包括i)

一维

// 预处理前缀和数组n+1
  pre[i] = pre[i - 1] + nums[i - 1];


// 计算 [i, j] 结果sum
 sum= pre[j] - pre[i - 1];

二维

1. pre数组同样变成二维

   
   image.png

2. 具体计算的时候就不用初始的matrix了，直接操作pre们

   
   image.png
   

   这个图表示缺了最小的那一块，还要加回去

• 所有变的操作都在小的那儿

class NumMatrix {
    int[][] matrix;
    int[][] pre;
    public NumMatrix(int[][] matrix) {
        this.matrix=matrix;
        int r=matrix.length;
        int c= r == 0 ? 0 : matrix[0].length;
          //构造pre
        pre=new int[r+1][c+1];
        for(int i=1;i<=r;i++){
            for(int j=1;j<=c;j++){
                //原则就是左上
                pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+matrix[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        //现在有了pre数组了
        return pre[row2+1][col2+1]+pre[row1][col1]-pre[row1][col2+1]-pre[row2+1][col1];
    }
    
}