C++ 2D Binary Index Tree


  • 0
    X
    class NumMatrix {
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            _row = matrix.size();
            if (0 == _row) return;
            _col = matrix[0].size();
            tree = vector<vector<int>>(_row + 1, vector<int>(_col + 1, 0));
            for (int i = 0; i < _row; i++) 
             for (int j = 0; j < _col; j++) {
                updateTree(i + 1, j + 1, matrix[i][j]);
            }
        }
        int sumRegion(int row1, int col1, int row2, int col2) {
            return read(row2 + 1, col2 + 1) - read(row1, col2 + 1) - read(row2 + 1, col1) + read(row1, col1);
        }
        
    private:
        vector<vector<int>> tree;
        int _row;
        int _col;
        
        void update(int row, int col, int val) {
            updateTree(row, col, val);
        }
        void updateTree(int row, int col, int val) {
            for (int i = row ; i <= _row; i += i & (-i)) 
              for (int j = col; j <= _col; j += j & (-j)) {
                    tree[i][j] += val;
            }
        }
        int read(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 += tree[i][j];
            }
            return sum;
        }
    };

Log in to reply
 

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