I can’t understand how to update the segment tree for range update through lazy propagation. I read almost all articles on lazy propagation but couldn’t find a suitable explanation. Please help.
Thanks
4 Likes
Here is a really nice explanation by @xellos0 . Although I strongly recommend looking at code of lazy propagation because in my case only looking at the code of lazy propagation helped. It actually looked quite trivial to me after looking at the code. Here is my code for spoj problem HORRIBLE. Its not commented but I used full names for variables so it should be easy to understand 
7 Likes
All that’s nice but could you just theoritacally explain me what lazy propagation does. Please don’t give any external links, I have visited them.
lazy propagation basically means that you update the node of the segment tree only when you need to.
No I mean can you give steps of lazy propagation.
suppose you get a query to update range [1,n]. In a normal segment tree you will first update 1, then 2 upto n which will take n*log(n) time but in lazy propagation we will update only the node which contains the sum of [1,n]. Now if we get a query asking for the sum of [1,n] we will return the value in the node that stores the sum of [1,n] and we know it will be correct because we updated it in the previous step. But suppose if we get a query asking for sum of [1,n/2] then what should we do . Simple we just carry the previous update we did on node storing sum of [1,n] to its children which
2 Likes
store the sum of [1, n/2] and [n/2+1, n] and now we can answer the query asking for the sum of [1,n/2].In a general query of [a,b] we may have to update at most log(n) nodes hence we have reduced the time to update from n*log(n) to log(n). Take a look at the implementation to understand it better
2 Likes