# An AC 1724 ms C++ solution, used Binary Indexed Trees

• ・What is "Binary Indexed Trees": http://blog.csdn.net/pi9nc/article/details/9006485

・The solution is really hard to explain, pls spend time on learning "Binary Indexed Trees".

``````class NumArray
{
private:
vector<int> n; //n used to copy input number array.
vector<int> tree; //tree[idx]=s[idx- 2^r + 1]+...+s[idx]; for example if idx=12=1100, there are two '0' after rightest '1', then r=2.
int sz;
public:
NumArray(vector<int> &s)
{
if (s.empty())
return;
n = s;
int idx, i, sum; //should note that idx started from 1, so if idx=2, it refer to the n[1].
sz = s.size();
vector<int> v(sz + 1, 0);
for (idx = 1; idx <= sz; ++idx)
{
sum = 0;
int one = -idx & idx; //-idx & idx used to calculate the value of last '1', for example, idx = 12= 1100, one = 100=4.
for (i = idx - one; i < idx; ++i)
sum += s[i];
v[idx] = sum;
}
tree = v;
}

void update(int i, int val)
{
if (i < 0 || i >= sz)
return;
int dif = val - n[i];
n[i] = val;
int idx = i + 1;
for (; idx <= sz;)
{
tree[idx] += dif;
idx += -idx & idx;
}
}

int sumRange(int i, int j)
{
if (i == j)
return n[i];
int a, b, idx;
a = b = 0;
for (idx = j + 1; idx;)
{
b += tree[idx];
idx -= -idx & idx;
}
if (0 == i)
return b;
for (idx = i; idx;)
{
a += tree[idx];
idx -= -idx & idx;
}
return b - a;
}
};``````

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