# C++_Binary Index Tree (Recommended Video)

• ``````class NumArray {
private:
vector<int> _nums;//to store the input int vector: nums
vector<int> bit;//Binary Index Tree! To store the subarray sum of nums

int lower_bit(int i){
return i&(-i);// To get the lowest 1 in this integer, this will be used for find the parent node and child node
}

int query(int i){//This function will be used to return the sum of 0 to i in nums (also _nums)
i++;//because in BIT, we calculate the index from 1, so add 1 to i.
int sum = 0;
while(i > 0){
sum +=  bit[i];
i = i - lower_bit(i);//flip the lowest 1 to go back to the parent node till the root.
}
return sum;
}

void add(int i, int val){//add value "val" in the bit vector.
i++;
while(i < bit.size()){
bit[i] += val;
i += lower_bit(i);//We should also update all of the child nodes of this parent node
}
}

public:
NumArray(vector<int> &nums) {
_nums = nums;
bit.resize(nums.size() + 1);
for(int i = 0; i < nums.size(); 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);

}
};``````

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