Codeforces и Polygon могут быть недоступны в период с 6 декабря, 22:00 (МСК) по 7 декабря, 00:00 (МСК) в связи с проведением технических работ. ×

Segment tree complexity when not merging lazy updates

Правка en1, от 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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский quinoa 2021-01-01 20:31:10 1475 Initial revision (published)