Can anyone explain segment tree with lazy propagation as I couldn’t get it & how is it faster than segment tree as both are top down approaches ,so how is that lazy makes it faster
1 Like
lazy propagation take O(logn) time time to update an inteval…The differnce between normal segmented tree update and lazy propagation is as follows…
1.In normal segtree the update starts from root and all the nodes which included in the interval are updated by travelling from top to bottom
2.In lazy propagation the update starts from root and not every nodes which included in the interval are updated…Instead the parent node of the interval is update…and mark its children node to be updated…
3.Hence the update in lazy doesnt need to travel whole tree from top to bottom to update every nodes
…hope this will helps
4 Likes
u can refer these two sites to know more in detail http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html http://sportcoder.com/segment-trees-lazy-updates/ … These two links covers everything u need…i was been behind this data structure last 3 days…learn with patiance and understanding…it may take time to understand…never give up…all the best 
5 Likes
thnx was great help…