# Share my c++ solution: 1700ms, using tree array

• ``````class NumArray {
public:
NumArray(vector<int> &nums) {
sz = nums.size();
num = vector<int>(sz+1, 0);
sum = vector<int>(sz+1, 0);
for(int i=0; i<sz; i++) {
update(i, nums[i]);
}

}

void update(int idx, int val) {
int oldv = num[idx+1];
for(int i = idx+1; i<=sz; i+= (i&-i)) {
sum[i] = sum[i] - oldv + val;
}
num[idx+1] = val;
}

int sumRange(int i, int j) {
return getSum(j+1) - getSum(i);
}

int getSum(int idx) {
int ret = 0;
for(int i=idx; i>0; i-=(i&-i)) {
ret += sum[i];
}
return ret;
}
private :
int sz;
vector<int> num;
vector<int> sum;
};
``````

log(n) to update, log(n) to sum

• Could you explain i&-i and why this is log(n)?

• This is a data structure called Binary Indexed Tree. It can be viewed as a degenerated segment tree.

• i & -i get the right most 1 in the binary i;

for example :i = 6

00000110

11111001 + 1 = 11111010

6&-6 = 2;

so that

for(int i = idx+1; i<=sz; i+= (i&-i))

in each iteration, i change the right most 1 to 0, so at most log(n) iterations.

• You are not using the tree at all....

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