how to solve funny marbles by BIT (Fenwick trees)

general
, ,
1

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

4 Likes
2

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
3

can u make me started a bit…

4

can u please tell me how the tree looks like?

5

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

1 Like
6

@kuruma thanks a lot :slight_smile:

7

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

8

@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.

9

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.

10

Okay i’ll edit the post for calculating sum

11

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

12

I will prefer to read this tutorial


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

13

now getting wa

14

use long long to avoid overflow

15

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

16

Great work! glad i could help

17

Without you it was impossible :)thankyou :slight_smile:

1 Like
18

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

19

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

20

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

1 Like