308. Range Sum Query 2D - Mutable

https://leetcode.com/problems/range-sum-query-2d-mutable/description/

image.png

一般需要求一个区间的和，并且需要动态更新区间里的值。不是树状数组就是线段树了。这道题我用树状数组解了。

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);
    }