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.
was necessary some optimization to get AC with this idea? I've came up with a pretty similar solution but it exceeds time limit..
ReplyDeleteI 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.
ReplyDeleteactually, 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!
ReplyDeleteI am Happy as i did with BIT !!!! and got the Fastest sol till today :P
ReplyDeleteI 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.
Deleteit would be great help if anyone can elaborate how to solve the problem using BIT..
Deleteno wonder, BIT is way faster than recursive segment tree. but I love segment tree don't know why...
ReplyDeleteSir ,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!
ReplyDeleteThis might help
Deletehttp://letuskode.blogspot.in/2013/01/segtrees.html
Sir, can you plzz explain me the concept of lazy propagation in segment tree thoroughly with example as i m not getting it... thanks.!!
ReplyDeleteCan any body tell me the error in my code. It is showing wrong answer on spoj. I used lazy propogation.
ReplyDeleteCode is given at : http://ideone.com/0TiVOY
I tried to solve it using the same technique but I get wrong answer can you help me http://ideone.com/CgnaYq
ReplyDeleteDidn'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.
Deletehttps://github.com/cacophonix/SPOJ/blob/master/HORRIBLE.cpp
can u check my code please http://ideone.com/cDSRFH can't find the mistake
ReplyDelete