quinoa's blog

Segment tree complexity when not merging lazy updates
By quinoa, history, 4 years ago, In English

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.

  • Vote: I like it
  • +21
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

2 — ofc it is, you need a flag isSet in every vertex to understand what to do with lazy updates, problem: https://cses.fi/problemset/task/1735

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, I will try to implement it like you say

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

1 — yes, this is very bad. Imagine that you add $$$q$$$ such updates to the range $$$[1, n]$$$, and then query range $$$[i, i]$$$ for every $$$i$$$. During the course of answering queries you will have pushed the list of updates to every leaf. And then you have to evaluate every update at every leaf, which leads you to $$$\Omega(nq)$$$ operations.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Thanks, I think I get it now. My mistake was that I only looked at how many elements we add to the "propagation lists" when doing the range update. I think it is correct that we will add $$$log N$$$ operations in the worst case which is OK.

    Like you say however, for the queries you might need to push $$$Q * log N$$$ elements down for a single query. And this could happen for every query, like in your example. This would cause $$$Q * N * log N$$$ number of push downs I think since there are $$$N * log N$$$ nodes in the segment tree and we will end up pushing the updates to every single node.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +19 Vote: I do not like it

(2) Yes, it is possible like dalex mentioned. I was stuck on the same problem for days before coming up with the right idea and have spent a lot of productive hours into it. I couldn't get a working implementation myself. With help from DenjellBoone, I finally managed to get an AC on CF EDU. Same problem on CSES. You can also read our discussion on Discord. I'd like to note that the discussion is incomplete as we continued a lot in personal DM. I would love to explain the idea in more detail if you have any doubts.

Here's a sample implementation for reference:

Code

I've tried maintaining propagation lists for each node but the solution ends up consuming too much memory. This solution that Denjell managed to implement has helped both of us in thinking about the general structure for lazy stuff on Segment Trees.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Great thanks. I will try to implement it myself and can use your implementation as a reference if I'm stuck

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Without even reading anything else from your blog- $$$O(K*log(N)*log(N))$$$ is actually $$$O(K*log^2N)$$$

Regarding question 2:

Yes, it's possible. Hint: the update is a pair of integer, boolean. The boolean flag determines whether the update is of set type or add type. You need to write all 4 cases of combining the updates (set,set) (set,add) (add,set) (add,add)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I implemented it like you said and got AC on the CSES problem listed by Lost_Arrow so seems to work. Thanks!

    → Reply