Need Help in Lazy Propogation!

Hello Codechef Users!

I need Help in Lazy Propogation. I have clearly understood segment-trees.

Please anyone instead of posting Links as an answer, if you can explain, it will be very helpful!

Thanks in Advance :slight_smile:

Basic Idea how lazy progation works is given below.

Taken from - http://www.spoj.com/forum/viewtopic.php?f=27&t=8296

Lazy Propagation means that you only update what you actually need to, when you need to.

For example, if we have a segment tree that covers the range 1-20. If we update segment [1,20], we update only the value of the root node of the tree and set a flag on it’s children [1,10] and [11,20] to let them know that they need to be updated.

Next, if we query [6,7] then when we reach a node in the traversal that has the update flag on, we need to flag it’s children and update it’s value.

[1,10] is flagged for update
query [6,7]
Traversal Route:
[1,10] - push update flag to [1,5] and [6,10] and update value of [1,10]
[6,10] - push update flag to [6,8] and [9,10] and update value of [6,10]
[6.8] - push update flag to [6,7] and [8,8] and update value of [6,8]
[6,7] - push update flag to [6,6] and [7,7] and update value of [6,7]

This leaves [1,5], [6,6], [7,7], [8,8], [9,10] flagged for update.

Its easy to understand if you just try it on a paper.

For its program - just google it you will get.

Hope it helps - Happy Coding!!

1 Like

hello bradley:

first thing about lazy propagation is that you do not need to update any child node unless such type of query/update occur(when node is not completely inside query/update range) that’s why it is fast because in case of query control always take value from parent node if it is completely inside query range. in case of update if parent is completely inside update range then OK modification will be on parent node and lazy value passes to its children if parent is not completely inside update range then control goes to children of that node and if child is completely inside range then child will be updated and lazy value passes to its children. If next time these children/child node is not completely inside query/update range then control will go inside these children/child node and now again check children of current node is completely inside range or not if yes then update and pass lazy value to its children if not then control again go inside and so on. Means explanation in one line WHEN YOU NEED THEN UPDATE. i hope it would help you.

if you have any doubt then you may ask :slight_smile:

Yes Brother! I clearly understood what I really need to do!
Thanks a lot! :slight_smile: