# C++ summary for the BIT Problem Set

• Range Sum Query

Solution 1

``````class NumArray {
public:
NumArray(vector<int> &nums) {
num.resize(nums.size() + 1);
bit.resize(nums.size() + 1);
for (int i = 0; i < nums.size(); ++i) {
update(i, nums[i]);
}
}
void update(int i, int val) {
int diff = val - num[i + 1];
for (int j = i + 1; j < num.size(); j += (j&-j)) {
bit[j] += diff;
}
num[i + 1] = val;
}
int sumRange(int i, int j) {
return getSum(j + 1) - getSum(i);
}
int getSum(int i) {
int res = 0;
for (int j = i; j > 0; j -= (j&-j)) {
res += bit[j];
}
return res;
}

private:
vector<int> num;
vector<int> bit;
};
``````

Solution 2

`````` class NumArray {
private:
vector<int> _nums;
vector<int> bit;

int lower_bit(int i){
return i&-i;
}

int query(int i){
i++;
int sum=0;
while(i>0){
sum+=bit[i];
i-=lower_bit(i);
}
return sum;
}

void add(int i, int val){
i++;
while(i<bit.size()){
bit[i]+=val;
i+=lower_bit(i);
}
}

public:
NumArray(vector<int> &nums) : _nums(nums) {
bit.resize(nums.size()+1);
for(int i=0; i<nums.size(); i++){
add(i, nums[i]);
}
}

void update(int i, int val) {
if(val!=_nums[i]){
add(i, val-_nums[i]);
_nums[i]=val;
}
}

int sumRange(int i, int j) {
return query(j)-query(i-1);
}
};
``````

Range Sum Query 2D - Mutable

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

void update(int row, int col, int val) {
int diff = val - mat[row + 1][col + 1];
for (int i = row + 1; i < mat.size(); i += i&-i) {
for (int j = col + 1; j < mat[i].size(); j += j&-j) {
bit[i][j] += diff;
}
}
mat[row + 1][col + 1] = val;
}

int sumRegion(int row1, int col1, int row2, int col2) {
return getSum(row2 + 1, col2 + 1) - getSum(row1, col2 + 1) - getSum(row2 + 1, col1) + getSum(row1, col1);
}

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

private:
vector<vector<int>> mat;
vector<vector<int>> bit;
};
``````

Count of smaller numbers after itself

``````class Solution {
public:
vector<int> countSmaller(vector<int>& nums) {
vector<int> t, res(nums.size());
for (int i = nums.size() - 1; i >= 0; --i) {
int left = 0, right = t.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (t[mid] >= nums[i]) right = mid;
else left = mid + 1;
}
res[i] = right;
t.insert(t.begin() + right, nums[i]);
}
return res;
}
};
``````

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