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.