# 2D BIT solution in C++(for practice), 284ms

• ``````class NumMatrix {
public:
NumMatrix(vector<vector<int>> &matrix) {
if (matrix.empty()) {
return;
}
for (int i = 0; i <= matrix.size(); i++) {
c.push_back(vector<int>(matrix[0].size() + 1, 0));
}
for (int i = 0; i < matrix.size(); i++) {
for (int j = 0; j < matrix[0].size(); j++) {
update(i + 1, j + 1, matrix[i][j]);
}
}

}

int sumRegion(int row1, int col1, int row2, int col2) {
int a = read(row2 + 1, col2 + 1);
int b = read(row2 + 1, col1);
int c = read(row1, col2 + 1);
return a - b - c + d;
}
private:
vector<vector<int> > c;
int lowbit(int x) {
return x & (-x);
}
void update(int idi, int idj, int diff) {
for (int i = idi; i < c.size(); i += lowbit(i)) {
for (int j = idj; j < c[0].size(); j += lowbit(j)) {
c[i][j] += diff;
}
}
}
int read(int idi, int idj) {
int res = 0;
for (int i = idi; i > 0; i -= lowbit(i)) {
for (int j = idj; j > 0; j -= lowbit(j)) {
res += c[i][j];
}
}
return res;
}
};``````

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