Can anyone please this doubt about segment tree?



I am learning segment trees, everything was going fine until I didn’t read about lazy propagation. I understood the idea behind the lazy propagation but I didn’t understand how it’s complexity is O(log N) in case of query. I explored various sources but didn’t find satisfactory justification for its complexity. Can anyone please explain in detail how its complexity is O(log N) in case of query.


It is same as the segment tree without lazy propagation. We only update the node which we visit during the query case and pass the updates to there children. So i think it take O(1).


In regular segment tree, we visit the highest nodes that are included in the query range. In lazy propagation, those same nodes are visited during the update range operation, but we add a lazy tag of those nodes so we can propagate the update when needed. Since we are doing the same amount of work in the update operation, the time complexity must be O(log N). However, the downside is that the new values for the highest nodes that are updated has to be able to be calculated directly, without looking at its children nodes.