You are not logged in. Please login at to post your questions!


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.

asked 18 Mar '18, 21:53

arpit728's gravatar image

accept rate: 10%

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).


answered 19 Mar '18, 01:56

ashudeshwal's gravatar image

accept rate: 0%

edited 19 Mar '18, 01:57

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.


answered 19 Mar '18, 07:44

c0deb0t's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 18 Mar '18, 21:53

question was seen: 252 times

last updated: 19 Mar '18, 07:44