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:
lazy_update(A) perform update on subtree A.
here we only record the update in node A.
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.