You are not logged in. Please login at www.codechef.com 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

1★arpit728
6831563
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).

link

answered 19 Mar '18, 01:56

ashudeshwal's gravatar image

3★ashudeshwal
302
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.

link

answered 19 Mar '18, 07:44

c0deb0t's gravatar image

4★c0deb0t
414
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×1,727
×1,650
×164
×141

question asked: 18 Mar '18, 21:53

question was seen: 252 times

last updated: 19 Mar '18, 07:44