https://leetcode.com/problems/range-sum-query-2d-mutable/description/
image.png
一般需要求一個區(qū)間的和昆雀，并且需要動態(tài)更新區(qū)間里的值湿滓。不是樹狀數(shù)組就是線段樹了。這道題我用樹狀數(shù)組解了。
int[][] parent;
int[][] ma;
int h;
int l;
private int lowbit(int i){ return i & (-i); }
private void add(int y,int x,int delta){
y++;x++;
for(int i = y; i<=h; i+=lowbit(i)){
for(int j = x; j<=l; j+=lowbit(j)){
parent[i][j] += delta;
}
}
}
private int query(int y,int x){
y++;x++;
int sum = 0;
for(int i = y; i>=1; i-=lowbit(i)){
for(int j = x; j>=1; j-=lowbit(j)){
sum+=parent[i][j];
}
}
return sum;
}
public NumMatrix(int[][] matrix) {
h = matrix.length;
if(h == 0) return;
l = matrix[0].length;
ma = matrix;
parent = new int[h+1][l+1];
for(int i = 0; i < h; i++){
for(int j = 0; j< l;j++)
add(i,j,ma[i][j]);
}
}
public void update(int row, int col, int val) {
add(row,col,val-ma[row][col]);
ma[row][col] = val;
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return query(row2,col2)+query(row1-1,col1-1)-query(row1-1,col2)-query(row2,col1-1);
}
