# how to solve funny marbles by BIT (Fenwick trees)

I confess that i have not at all being able to get binary indexed trees.
I browsed through number of tutorials(topcoder,codeforces,etc)but i didn’t get it still.

It would be great if someone can explain it so that atleast i get started.

5 Likes

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.

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

4 Likes

can u make me started a bit…

can u please tell me how the tree looks like?

1 Like

@kuruma thanks a lot

@yashkumar18 can you tell me how to calculate ft[1…n]?

@anonymousins for the sake of understanding dont take it as a tree it just an array of size equal to the size of ur given array …the differnce is simply this array(fenwick tree) stroes the cumulative information .may this help u.

Why would anyone downvote this question. Just a few hours ago this had 1 upvote but now it had 0 upvotes before I upvoted it again.

Okay i’ll edit the post for calculating sum

Is this implementation correct? http://ideone.com/9z6CCw

I will prefer to read this tutorial

and solution is http://www.codechef.com/viewsolution/3050032

2 Likes

now getting wa

use long long to avoid overflow

Thankyou got an AC http://www.codechef.com/viewsolution/3151085

Great work! glad i could help

Without you it was impossible :)thankyou

1 Like

@yashkumar18 i have one doubt…i initialised ft[0…n]=0 as it is required…now unitialised it and still got an AC.How?

Because when delcared globally, all elements =0 already , but not so when declared inside main, see this -> http://ideone.com/Nc7pzo , http://ideone.com/VMK4SE

http://codeforces.com/blog/entry/619
Try this… just look at it believe me…it might help.

1 Like
//