yet another 2d BIT c++ solution


  • 0
    Y
    // this problem can be solved using 2d binary index tree,
    // compared with segment tree, BIT uses less memory,
    // the memory needed for BIT is proportional to the range,
    // also BIT is easy to implement,
    // however the idea of BIT might be tricky at the first glance
    //
    // update: O(logm*logn), m n represents matrix's range
    // sumRegion: O(logm*logn)
    // space: O(m*n)
    //
    // inspired by following link:
    // https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/#2d
    //
    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            if (matrix.size() == 0 || matrix[0].size() == 0) return;
            matrix_ = vector<vector<int>>(matrix.size(), vector<int>(matrix[0].size()));
            tree_ = vector<vector<int>>(matrix.size() + 1, vector<int>(matrix[0].size() + 1));
            for (int i = 0; i < matrix.size(); ++i) {
                for (int j = 0; j < matrix[0].size(); ++j) {
                    // this will build tree from ground up
                    // adding matrix val to corresponding ranges while iterating
                    update(i, j, matrix[i][j]);
                }
            }
        }
    
        // basic BIT update
        // start from idx (here it is 2d) following idx(i+1) = idx(i) + 2^(last bit of idx(i)) until reach boundary
        // apply diff to tree[idx(i)], tree[idx(i+1)], ...
        void update(int row, int col, int val) {
            int diff = val - matrix_[row][col];
            for (int i = row + 1; i <= matrix_.size(); i += i & -i) {
                for (int j = col + 1; j <= matrix_[0].size(); j += j & -j) {
                    tree_[i][j] += diff;
                }
            }
            matrix_[row][col] = val;
        }
        
        // same as the immutable question
        // sum(row2, col2) - sum(row2, col1-1) - sum(row1-1, col2) + sum(row1-1, col1-1)
        int sumRegion(int row1, int col1, int row2, int col2) {
            return sumRegion(row2, col2) - sumRegion(row2, col1 - 1) -
                     sumRegion(row1 - 1, col2) + sumRegion(row1 - 1, col1 - 1);
        }
        
    private:
        // basic BIT read cumulative
        // start from idx (here it is 2d) following idx(i+1) = idx(i) - 2^(last bit of idx(i)) until reach 0
        // tree[idx(i)] + tree[idx(i+1)] + ... will be the cumulative value
        int sumRegion(int row, int col) {
            int sum = 0;
            for (int i = row + 1; i > 0; i -= i & -i) {
                for (int j = col + 1; j > 0; j -= j & -j) {
                    sum += tree_[i][j];
                }
            }
            return sum;
        }
    
        vector<vector<int>> matrix_;
        vector<vector<int>> tree_;
    };
    

Log in to reply
 

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