Please correct my implementation of Binary Indexed Tree

I am getting RTE with this code http://www.codechef.com/viewplaintext/3150374
I think there’s something wrong with my implementation. I studied BIT from here : http://karthikpresumes.blogspot.in/2011/01/binary-indexed-tree.html

Problem link : Funny Marbles

I guess you are getting SIGSEGV because you are declaring your array array locally as int array[1000050] = {0};. Declare it globally and try.

1 Like

No that’s not the error

Tried it. Still getting RTE.

you are creating two arrays of size 10^6 and they have to handle long int’s so the program runs out of memory…

so instead of declaring two arrays try declaring only one array BIT[10^6} and don’t store the input

instead of storing the input insert each element into the BIT right away when you take the input

logically your program is correct

pseudo code :

declare BIT
take input each element at a time:
      insert that element in BIT
Now do remaining according to queries.

I Faced the same problem and I’m sure that above logic will work…

RTE again : http://www.codechef.com/viewplaintext/3150822

//