前缀和
区间和 记住一个n+1(方便操作) i-1(因为是和相减，所以不能包括i)
一维
// 预处理前缀和数组n+1
pre[i] = pre[i - 1] + nums[i - 1];
// 计算 [i, j] 结果sum
sum= pre[j] - pre[i - 1];
二维
-
pre数组同样变成二维
image.png -
具体计算的时候就不用初始的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];
}
}
