# share two of my solution using Java(segment tree and BIT)!

• The first is to use segment tree:

``````public class NumMatrix {
int[][] treenodes;
int collen;
int rowlen;
public NumMatrix(int[][] matrix) {
if(matrix==null||matrix.length<1) return;
rowlen=matrix.length;
collen=matrix[0].length;
treenodes=new int[rowlen][collen*2];
for(int i=0;i<rowlen;i++){
for(int j=0;j<collen;j++){
treenodes[i][collen+j]=matrix[i][j];
}
for(int j=collen-1;j>=0;j--){
treenodes[i][j]=treenodes[i][j<<1]+treenodes[i][(j<<1)|1];
}
}
}

public void update(int row, int col, int val) {
int j=col+collen;
int dif=val-treenodes[row][j];
while(j>0){
treenodes[row][j]+=dif;
j>>=1;
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {
int sum=0;
for(int row=row1;row<=row2;row++){
int i=col1+collen;
int j=col2+collen;
for(;i<=j;i>>=1,j>>=1){
if((i&1)==1){
sum+=treenodes[row][i];
i++;
}
if((j&1)==0){
sum+=treenodes[row][j];
j--;
}
}
}
return sum;
}
}
``````

The second is to use binary indexed tree which can improve the efficiency:

``````
public class NumMatrix {
int[][] treenodes;
int[][] nums;
int collen;
int rowlen;

public NumMatrix(int[][] matrix) {
if(matrix==null||matrix.length<1) return;

this.rowlen=matrix.length;
this.collen=matrix[0].length;
this.nums=new int[rowlen][collen];

treenodes=new int[rowlen+1][collen+1];
for(int i=0;i<rowlen;i++){
for(int j=0;j<collen;j++){
update(i,j,matrix[i][j]);
}
}
}

public void update(int row, int col, int val) {
int i=row+1;
int j=col+1;

int dif=val-nums[row][col];
this.nums[row][col]=val;
while(i<=rowlen){
j=col+1;
while(j<=collen){
treenodes[i][j]+=dif;
j+=(j&(-j));
}
i+=(i&(-i));
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {
return upperleftsum(row2,col2)+upperleftsum(row1-1,col1-1)-upperleftsum(row1-1,col2)-upperleftsum(row2,col1-1);
}

public int upperleftsum(int row,int col){
if(col<0) return 0;
if(row<0) return 0;
int i=row+1;
int j=col+1;
int sum=0;
while(i>0){
j=col+1;
while(j>0){
sum+=treenodes[i][j];
j-=(j&(-j));
}
i-=(i&(-i));
}
return sum;
}
}

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.