# Short Binary Indexed tree (BIT or Fenwick tree) based C++ solution (1720 ms)

• You can do

• O(1) update, O(N) sumRange
• O(N) update, O(1) sumRange
• O(NlogN) update, O(NlogN) sumRange

Since here, the update and sumRange operations are distributed evenly, option 3 is more appropriate. Basically, we can use a segment tree to achieve that. For this speical case, we can use a simplified version: binary indexed tree (BIT), in which a linear array BITSum is used and the "pointers" can be calculted directly as array indices. BITSum[i] is the sum of num[i-x+1::i] (note i starts from 1), where x is the value respresented by the rightmost "1" bit of i (e.g. i=5 =>x=1; i=4=>x=4). x can be calculated as x = i - i &-i (i &-i reset the rightmost "1" bit to 0). More details can be found online.

``````class NumArray {
private:
int nSize;
vector<int> BITsum; // BIT sum array
vector<int> num; // original nums array

int getSum(int i)
{
if(i<=0 || i>nSize) return 0;
int res=BITsum[i];
while( (i -= i & -i) > 0 )
res +=BITsum[i];
return res;
}
public:
NumArray(vector<int> &nums) {
nSize = nums.size();
num = BITsum = vector<int>(nSize+1, 0);
for(int i=0;i<nSize; ++i)
update(i, nums[i]);
}

void update(int i, int val) {
int delta = val - num[++i];
for(num[i] = val;i<=nSize;i += i & -i)
BITsum[i] +=delta;
}

int sumRange(int i, int j) {
return (i>j || i<0 || j>=nSize)? 0: i==j?num[i+1]:( getSum(j+1) - getSum(i) );
}
};``````

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