I’ll try my best, I didn’t know anything about fenwick trees too, but i learned it during the contest itself and came up with a very clean simple solution, first try to read my solution, it should be pretty clear : http://www.codechef.com/viewsolution/3043721

Then see the image at topcoder tutorial and understand what (i&-i) does, then it should be pretty clear.Pick a pen and paper and solve an example by drawing the tree, it will help trust me.

Feel free to ask anything

EDIT:—

Okay, for a start lets say your array is arr[1,2,3,4,5,6,7,6,5,4,3,2,1,2,3,4] - 16 elements

now you have a array representing the tree of 10 elements as well, say Ftree[16], now consider this image from topcoder tutorial

![alt text][1]

In case you don’t understand the concept, see the 8th element for example, it covers all the elements [1,8] i,e Ftree[8] = arr[1]+arr[2]+…+arr[8]

Similarly Ftree[14] = arr[14]+arr[13] and Ftree[15] = arr[15]

That should clear the idea of the tree structure

**Now, how to construct the tree?**

lets say you are adding the 6th element during construction, first you add arr[6] to Ftree[6] and the to all the elements of the tree that are supposed to contain the sum of 6th element i.e Ftree[8] and Ftree[16], this is where (i&-i) (side note: ill leave it upto you how this statement works) comes in

So, you are adding 6th element, say ‘i’ stores the index (i=6) for you do Ftree[i]+=arr[6],

Now the statement

```
i+=i&-i
```

“magically” makes i=8 so again you do Ftree[i]+=arr[6]

Again the statement i+=i&-i makes i=16 and you keep doing this as long as i<size of tree(16 in this case)

Hope It helps

EDIT:—

**Calculating sum 1st to nth element**

Here is the code

```
int Sum(int n)
{
int res=0;
while(n>0)
{
res+=Ftree[n];
n-=(n&-n);
}
return res;
}
```

It’s that simple. Plus, for range sum ftree[i…j] = Sum(j)-Sum(i-1)

[1]: http://community.topcoder.com/i/education/binaryIndexedTrees/BITimg.gif