i understood segmented tree…but nowher i can see clear explanations of “LAZY PROPAGATION”…i searched topcoder,geeksforgeeks and all possible blogs and forums…Is ther any book on advanced data structures??..i want to clearly understand this lazy propagation…pls help…thanks…
3 Likes
Ok, here I go.
Consider a standard interval tree (usually called segment tree, but I use a transliteration from the Slovak term), which supports operations “set the value of node i to v” and “return the maximum value from the interval [u,v)” (semi-closed intervals are comfortable to use). This tree keeps the following information in a node: the interval [u_i,v_i), the maximum value from this interval and at most two sons of this node.
Updates are done recursively: after the value in one of a node’s sons is updated, the value in the node itself is updated. Queries are answered this way: you always query on (node,interval), where interval is the subinterval of the one [v_i,u_i) in the node. If interval is empty, the answer’s trivial; if it’s equal to [v_i,u_i), it’s just value of the node and otherwise, you compute it recursively.
Now, what does lazy propagation (lazy-loading is the Slovak transliteration) do? You don’t update “one node to value v”, but “interval [x,y) to all values equal to v”. You also add one more value to each node: the modifier, and a single function modify(node). The modifier holds the following information: “all elements in this interval are actually equal to x” or “ignore this” (if there’s no fitting x, for example during initialization). The modify() function updates all sons’ modifiers to this one (we need to make sure that the modifier of an ancestor has higher priority than the one of a son), sets the value in the node equal to the modifier and changes modifier to “ignore”, to avoid collisions with later updates. This basically processes all updates in the given node, but not in the underlying subtree.
Before any call of functions update() or query(), you call modify() on this node. That way, you’ll be certain that earlier updates in this node have been processed and there can’t be any collisions.
Notice that query() hardly changes. You still do the same, just with calling modify() beforehand on the node on which you call query(), and time complexity stays the same: O(log N).
Updating changes a bit, because it affects the modifier. Firstly, update(node,interval) is also called with interval being a subinterval of the one in the node. It’s called in a similar way to update(): if interval is empty, just return from the function call; if it’s the whole interval stored in the node, all elements are updated to the same value, which means you only change the modifier and return; the rest of the work would be done when any function is called on this node later on. And in the last other case, with interval being a non-trivial one, you call update() on the sons (if the interval is non-trivial, both exist), set value to their maximum and return. Just remember: don’t forget to call modify(node) before update(node,interval) or query(node,interval).
We can see that any function call only takes O(1) time. The trick is in the width of recursion. It can be shown that if both recursive calls (whether of update() or query()) are non-trivial, then it won’t happen again, which means no further recursive branching to depth larger than 1, and therefore O(tree depth)=O(log N) calls (or time).
There are many other variants of lazy-loaded interval trees, which depend on the types of updates and queries, and on the number of them - it’s possible to have two types of updates or of queries, etc., but you need to handle specific commands in specific order to avoid collisions, and it’s quite complicated.
27 Likes
@xello…reali thanks for the explanation…also i got a aother source to leaern this concept here http://sportcoder.com/segment-trees-lazy-updates/
Can you please explain this sentence: all elements in this interval are actually equal to x" or “ignore this” (if there’s no fitting x, for example during initialization). From what I get, the x should be v instead.
dead link…
6 Likes
For certain types of segment trees, range updates are possible. Consider, for example, a variation in the range minimum query problem in which we can not only update individual elements but also request that every element in a given range be set to the same specified value. This would be known as a range update. Lazy propagation is a technique that allows range updates to be carried out with the same asymptotic time complexity, \mathcal{O}(\lg N), as individual updates.
The technique works as follows: each node contains an additional lazy field, which will be used for temporary storage. When this field is not being used, its value will be set to +\infty. When updating a range, we select the same set of nodes that we would select if querying that range, and update their lazy fields to the desired value (that is, we set them to the new value if the new value is lower), except for leaf nodes, whose values are immediately set to the new value. When a query or update operation requires us to access a proper descendant of any node whose lazy field is set (i.e. not +\infty), we “push” the lazy field onto the two children: that is, we update the children’s lazy fields according to the parent’s and reset the parent’s to +\infty. If, however, we access the node without accessing any of its proper descendants, and the lazy field is set, we simply use the value of the lazy field as the minimum for that node’s associated interval.
refer here for more How to implement segment trees with lazy propagation?
Hey guys if segment tree with lazy propagation is still a mystery for you please check this link http://www.logikx.in/2015/08/27/segment-trees-with-lazy-propogation-2/
1 Like
Refer the above two links to understand more about Lazy Propagation.
Refer the above two links to understand more about Lazy Propagation.
1 Like
This article explains the lazy propagation in Segment tree quite clearly. Also a lot of comments in code makes it easy to understand. You can find the article at https://techienotes.info/2015/09/01/lazy-propagation-in-segment-tree/
Usefull links for understanding lazy propagation, thanks.
Great tutorial ! Awesome.
Keep adding more tutorials man ! (Y)
Can anyone give a more tough example than finding sum or max/min as I am not able to do more difficult ones?