# yet another 2d BIT c++ solution

• ``````// 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)
//
// 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:
// 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_;
};
``````

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