Tuesday, 13 January 2015

segment tree laze propagation


reference :- spoj forum



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.