Блог пользователя vsanjay_nitdgp

binary indexed tree--spoj
Автор vsanjay_nitdgp, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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!

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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://mirror.codeforces.com/blog/entry/6779 problem: Little Girl and Maximum Sum.

Hope this helps!

→ Ответить