LAZY PROPAGATION IN SEGMENT TREES

I am somewhat clear with what lazy propagation is and why it is used.

I referred the following links:


http://discuss.codechef.com/questions/25582/codechef-question-multiples-of-3

Similar to the last link, I also coded the same solution, which obviously gives TLE. But I am unable to understand how to code for lazy propagation. Can someone lease help!!

1 Like

Maybe if you tried searching here…

1 Like

To my understanding, lazy propagation is to record the update to a whole subtree, and perform update only when needed.

On a range update, record the update to a whole sub tree in the root node of subtree;

On a query, perform all recorded updates from root to the query node.

If on update, the exact value is required (eg. update maximum), perform all recorded updates from root as well.

Suppose AL, AR are child nodes of A, and X, Y are child nodes of AR. Perform following 2 operations:

  1. lazy_update(A) perform update on subtree A.
    here we only record the update in node A.

  2. query(X) perform a query on X.
    we perform lookup from the top.
    when encounter A, we perform the lazy update on A, and break it into lazy_update(AL) and lazy_update(AR).
    when encounter AR, we perform the lazy update on A, and break it into lazy_update(X) and lazy_update(Y).
    Finally, we perform update on X, and query the final value.

Here to query(X), we break lazy_update(A) into lazy_update(AL), lazy_update(X) and lazy_update(Y)

One critical point of lazy update is to record update on node in O(1) time and space, preventing recursive update on subtree.

for example, to find multiples of 3, we need to record the count of numbers with remainder 0/1/2 when divided by 3, say c0,c1,c2.
when update(2), numbers with remainder 0/1/2 become remainder 2/0/1. other updates are similar. so we can just swap the counts to complete the update.

1 Like

The thing i have understood is: Let’s say I have to get maximum of the given range and perform update queries, so I am storing the maximum of child nodes in a segment tree node. So, performing update, we can still get the maximum by any tree node by adding value without going to its root i.e. eg. if (0,3) i have to increment by 2, then incrementing tree[1] by 2 and marking tree[3] and tree[4] as lazy will do the required. The next time any update or query operation is performed first the nodes marked as lazy will be updated and then the operation will proceed. Am I wrong here.??

Also when I have to find multiples of 3, I am storing the count of numbers divisible by 3 in a tree node in the (left child, right child) range. So, how the same above thing can be applied here? I’ll have to traverse down till the root to check the current value of that root node and then update all the required nodes. There’s a large probability I am getting on the wrong way, But please correct me!!