Thursday, December 9, 2010

SPOJ - HORRIBLE



Problem 8002. Horrible Queries


Another nice problem by Iqram Mahmud.

This is a data structure related problem and can easily be solved by segment tree / range tree. At each node of the tree, we can keep the sum of all elements that falls in the current range, i.e. children of current node, and add which is the value which must be added when we pass through this node.

So, for the update query, we just find the exact interval and add the given additional value with current sum (Node->sum += interval * value) and add (Node->add += value). Then we recursively update sum of all its ancestors (Node->sum = Left->sum + Right->sum + interval * Node->add). Similarly, we can make the second query, we just keep adding the add values of each node we pass (call it carry), then when we are in the exact range, we return current sum + interval * carry.

Be careful, indexes are 1 based and the calculation may easily overflow 32 bit integer.

14 comments:

  1. was necessary some optimization to get AC with this idea? I've came up with a pretty similar solution but it exceeds time limit..

    ReplyDelete
  2. I wrote a plain recursive segment tree implementation, no optimization was needed. Make sure your update and query processes are not going through un-necessary branches.

    ReplyDelete
  3. actually, to get accepted i've needed to use an approach like yours. My update query even don't going thru unnecessary branches in the worst case was reconstructing the whole tree, what can be done just updating the first node with your approach. By the way, congratulations on your blog!

    ReplyDelete
  4. I am Happy as i did with BIT !!!! and got the Fastest sol till today :P

    ReplyDelete
    Replies
    1. I also solved HORRIBLE using segment tree, but I am really interested in learning the solution that uses a Binary Indexed Tree. The only thing I managed to achieve is to add a value in a range and ask for the i-th element (i.e. I coudn't manage the query of the sum of an interval). If you could give us some more information about your solution, please do so. Thank you in advance.

      Delete
    2. it would be great help if anyone can elaborate how to solve the problem using BIT..

      Delete
  5. no wonder, BIT is way faster than recursive segment tree. but I love segment tree don't know why...

    ReplyDelete
  6. Sir ,please write tutorials on segment tree and especially how to solve various spoj problem using it.. I read the segment tree from topcoder tutorials but i am not able to implement it on SPOJ problems.. Searched a lot of sites , but non of them were handy .Thanks!

    ReplyDelete
    Replies
    1. This might help
      http://letuskode.blogspot.in/2013/01/segtrees.html

      Delete
  7. Sir, can you plzz explain me the concept of lazy propagation in segment tree thoroughly with example as i m not getting it... thanks.!!

    ReplyDelete
  8. Can any body tell me the error in my code. It is showing wrong answer on spoj. I used lazy propogation.
    Code is given at : http://ideone.com/0TiVOY

    ReplyDelete
  9. I tried to solve it using the same technique but I get wrong answer can you help me http://ideone.com/CgnaYq

    ReplyDelete
    Replies
    1. Didn't run your code, but I think they way you are splitting left and right side is buggy. You can find my solution in the internet.
      https://github.com/cacophonix/SPOJ/blob/master/HORRIBLE.cpp

      Delete
  10. can u check my code please http://ideone.com/cDSRFH can't find the mistake

    ReplyDelete