Can anybody tell me for which type of range query we can apply lazy propagation on segment tree ?Like
I was Just Solving SPOJ Problem GSS4 where I have to modify number in given interval to the floor of it’s square root,so can I apply lazy propagation on this type of query . If yes ! then How ?.Thanks in Advance
Generally, lazy propagation is used when the number of nodes in the tree that will be affected by a query is large. eg. Adding a number ‘v’ to every position in the range. But this doesn’t mean that you can use this in all problems of this kind. In the example that I mentioned above, you’re able to use lazy propagation only because, when an update query appears, you know that for a node that contains ‘x’ elements, you will add x*v to that node, ie. this update does not depend on the ‘x’ individual numbers in the range.
That is not the case with this problem, suppose that a node has the sum of a few numbers, when an update query appears, you need to apply square root to all the numbers in the range, and get the new sum. You cannot do this without actually looking at every number in the range.
You can solve this problem by maintaining the minimum and sum in the range, and whenever an update query appears, you simply go to the bottom of the tree, and apply the square root to every individual number, but with a small condition, you will only update a node when the smallest number in its range ie., minimum is more than 1.This way, every node will be visited at most LgLgA (A is the largest number in the input) times, because if you apply square root to any number that many times, it will reach 1. This should be fast enough to get accepted.
4 Likes
Probably this can help :
Thanks! for your quick and clear response…
1 Like
Finaly i completed my implementaiton of the SPOJ GSS4 but I am getting TLE…Can you point out where i am making mistake .Here is my code link 7WZFKN - Online C++0x Compiler & Debugging Tool - Ideone.com