首页 > itarticle > binary index tree: range update and range queries

binary index tree: range update and range queries

admin 11月 13, 2020 0

1D binary index tree
2D binary index tree

Position of rightmost set bit

Get the rightmost set bit by “and”(&) x and -x.
Because getting -x by flipping every bit of x and plus 1.

1
2
3

int (int x){
   return log2(x & -x) + 1;
}

Basic Idea

update BITree: From leaf to root
get Sum with a arrangement: From root to leaf

2D binary index tree

LC 308. Range Sum Query 2D - Mutable

class NumMatrix {
public:
    vector<vector<int>> BItree;
    vector<vector<int>> nums;
    int r, c;
    NumMatrix(vector<vector<int>> matrix) {
        r = matrix.size();
        if(r == 0 || matrix[0].size() == 0)
            return;
        c = matrix[0].size();
        BItree = vector<vector<int>>(r+1, vector<int>(c+1, 0));
        nums = vector<vector<int>>(r, vector<int>(c, 0));
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                update(i, j, matrix[i][j]);
            }
        }
    }

    void update(int row, int col, int val) {
        if(r == 0 || c == 0)
            return;
        int delta = val - nums[row][col];
        nums[row][col] = val;
        for(int i = row+1; i <= r; i += (i & -i)){
            for(int j = col+1; j <= c; j += (j & -j)){
                BItree[i][j] += delta;
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        if(r == 0 || c == 0)
            return 0;
        return getSum(row2+1, col2+1) + getSum(row1, col1) - getSum(row1, col2+1) - getSum(row2+1, col1);
    }

    int getSum(int row, int col){
        int sum = 0;
        for(int i = row; i > 0; i -= (i & -i)){
            for(int j = col; j > 0; j -= (j & -j)){
                sum += BItree[i][j];
            }
        }
        return sum;
    }
};


 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * obj.update(row,col,val);
 * int param_2 = obj.sumRegion(row1,col1,row2,col2);
 */