Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Segment tree complexity when not merging lazy updates

Revision en1, by quinoa, 2021-01-01 20:31:10

After watching SecondThread's Segment tree tutorial I have the following questions:

Question 1: Not merging lazy updates

At this point in the video SecondThread mentions that you need to merge lazy updates for every node into a single update in order for the segment tree to stay $$$O(K * log N)$$$ time for $$$K$$$ queries. I don't understand why that is the case.

Imagine we have a segment tree implemented for range sums and we implement it such that every node has a list of lazy propagation operations (which SecondThread says is bad), instead of a single lazy propagation operation. So for instance if you add +3 to some range, and then add +5 to the same range you would have [+3, +5] as your operations for the corresponding node instead of +8.

Since every rangeAdd will add at most $$$log(N)$$$ of these operations to our lists, it means that in total we will have to push something down $$$O(K * log(N) * log(N)) = O(K * log(N))$$$ times. So the algorithmic complexity does not change. Am I wrong here?

Question 2: Combining "set to" and "add to" operations

Is it possible to make a segment tree that supports both "setting a range to some value" and "adding some value to a range"? I understand how to do each of those separately but I don't see how you can support them both.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English quinoa 2021-01-01 20:31:10 1475 Initial revision (published)