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
ReplyDeleteno wonder, BIT is way faster than recursive segment tree. but I love segment tree don't know why...
ReplyDelete