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.

Link for funny marbles

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.

Feel free to ask anything :smiley:

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 :slight_smile:

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

I will prefer to read this tutorial


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

2 Likes

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

1 Like

I solved the problem using Segment Trees. Wondering which one is more efficient for the Funny Marbles question: Fenwick or Segment?? I am not aware of Fenwick trees btw, so gunna spend my Sunday on this :smiley:
Strangely, I can’t find the editorials for the December long contest though

@lonecodertaken : u can find the editorials for the DEC13 here http://discuss.codechef.com/tags/dec13/

1 Like

can u make me started a bit…

can u please tell me how the tree looks like?

when Im home I’ll write a long tutorial about this :smiley:

1 Like

@kuruma thanks a lot :slight_smile:

@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

now getting wa

use long long to avoid overflow

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

Great work! glad i could help

Without you it was impossible :)thankyou :slight_smile:

1 Like