vsanjay_nitdgp's blog

binary indexed tree--spoj
By vsanjay_nitdgp, history, 9 years ago, In English

sir,,,i have just learnt how BIT works.....

i was trying to impliment the same for this problem :http://www.spoj.com/problems/HAYBALE/

but,i couldnt get idea how to do it,,,,,could anyone pls help me how to approach this problem using BIT..

thanks in advance.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You could solve it without BIT. Having an array of size N, and operation like add 1 to A..B, you can add 1 to A, and add -1 to B+1. After all operation, travel from 0 to N, doing something like RSQ (Range Sum Query), and you have the heights. Then I think you can handle it. Regards!

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please have a look at this blog. It has everything you need to solve the above question . Its not Binary Indexed Tree though (its about Segment Tree)

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

As facug91 pointed out, you can solve this problem without using a BIT or ST. For more information on the approach he pointed out, take a look at this editorial http://codeforces.com/blog/entry/6779 problem: Little Girl and Maximum Sum.

Hope this helps!

→ Reply