// package my;
public class NumMatrix {
public static void main(String[] args){
int[][] examp = new int[2][2];
NumMatrix obj = new NumMatrix(examp);
obj.update(0,0,1);
// System.out.println
int param_2 = obj.sumRegion(0,0,1,1);
System.out.println(param_2);
}
private int[][] matrix;
private int[][] sumcol; // sumcol[i][j] = sum{m[0][j]...sum[i-1][j]}
public NumMatrix(int[][] matrix) {
if( matrix == null
|| matrix.length == 0
|| matrix[0].length == 0 ){
return;
}
this.matrix = matrix;
int m = matrix.length;
int n = matrix[0].length;
sumcol = new int[m+1][n];
for(int j=0;j<n;j++){
for(int i=1;i<=m;i++){
this.sumcol[i][j] = this.sumcol[i-1][j] + matrix[i-1][j];
}
}
}
// O(m)
public void update(int row, int col, int val) {
this.matrix[row][col] = val;
int m = this.matrix.length;
for(int i=row+1;i<=m;i++){
this.sumcol[i][col] = this.sumcol[i-1][col] + matrix[i-1][col];
}
}
public int sumRegion(int row1, int col1,
int row2, int col2) {
int sum = 0;
for(int i=col1;i<=col2;i++){
sum += sumcol[row2+1][i] - sumcol[row1][i];
}
return sum;
}
}
