Most of the questions I have seen that can be solved with lazy propagation can also be solved with no propagation.
For example, for the problem referred you can just use an ordinary segment tree, where each node has two extra pieces of information: numberOfLightsOn and wholeRegionIsFlipped. When you flip a segment S=[l,r], the way you handle the segment corresponding to S1=[l1,r1] is: * if r<l1 or r1<l, S and S1 do not meet, so do nothing * if l1<=l and r<=r1, S1 is contained in S, so flip the Boolean flag wholeRegionIsFlipped, and set numberOfLightsOn to be (r1+1-l1)-numberOfLightsOn. * if neither of the above are true, S1 contains some elements in S and some elements not in S. Pass the information about the flip to the children of S1. When done, set numberOfLightsOn to be the sum of the children's numberOfLightsOn. There are only 2(log n) nodes in the tree that fit into Category 3 here, so this operation is done in time O(log n). When you query a segment S=[l,r], I guess the way you would handle the segment corresponding to S1=[l1,r1] (with lazy propagation) is: * if S1 has a true wholeRegionIsFlipped flag, flip the wholeRegionIsFlipped flag of the children nodes, invert the children nodes' numberOfLightsOn and set my wholeRegionIsFlipped flag to false And then, regardless of whether you did that: * If r<l1 or r1<l, S and S1 do not meet, so return 0. * If l1<=l and r1<=r, S1 is contained in S, so return numberOfLightsOn. * If neither of the above are true, S1 contains some elements in S and some elements not in S. Query the children nodes, and return the sum of the answers. But you could also do this without ever propagating the flipping information down as follows: Change the update operation so that when you flip the flag wholeRegionIsFlipped, you don't change numberOfLightsOn. Do not do the first step of the query operation (propagating wholeRegionIsFlipped) Change the bulk of the query operation to: * If r<l1 or r1<l, S and S1 do not meet, so return 0. * If l1<=l and r1<=r, S1 is contained in S, so return f(numberOfLightsOn). * If neither of the above are true, S1 contains some elements in S and some elements not in S. Query the children nodes, and return f(the sum of the answers). Here f(x) is x if wholeRegionIsFlipped is false, and (r1+1-l1)-x elsewise. I imagine there are problems that can be solved with lazy propagation, but cannot be solved with no propagation, but a cursory search using the web search site http://www.google.com did not reveal any. I haven't tried AltaVista or Lycos. Let me know if this makes sense. On 20 Oct 2012, at 18:37, sharad singh <[email protected]> wrote: > lazy propogation is used when ever you need to answer query with the change > in segment tree(change means updating values in given ranges not in the size > of tree ) ,lazy propogation will help you to update and answer the query in > the given tree with in logn time. > > refer problem http://www.spoj.pl/problems/LITE/ > > > > On Sat, Oct 20, 2012 at 7:53 PM, Sagar Gandhi <[email protected]> > wrote: > want to know about lazy propogation & how to use this method in > solving problems which cannot be solved easily by generally simple > segment tree !! > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit https://groups.google.com/groups/opt_out. > > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit https://groups.google.com/groups/opt_out.
