Restricted's blog

Question about Li Chao tree.
By Restricted, history, 20 months ago, In English

Hello codeforces!
I am trying to learn the Li Chao tree, but there is a part i am unable to understand. All the resources that i found (e.g: cp-algo) describe it by using two lines. With two lines, it makes sense, because one of them will dominate at most one of the two halves, and in this way, we would have to update only one half (similar to segment trees). Although, that is not always the case when there are more lines. I will describe what i mean with an example (check the image below). Let's say, that the blue lines were inserted before, and now we want to insert the red line. In our case, the red line dominates the green highlighted segment that is on both the left and right part of the total range. In the implementation that the sites provide, we always choose to move to one side and thus maintain logarithmic time. But in the case i describe, we should update both the left and the right part.
What am i missing?
Thanks!

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

»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In each segment you store only one line, not many.

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

    Yes, i understand that, but how does this change things? In the example above, wouldn't we still have to go through both children to update them? Previously, for the segments [L,MID] & (MID, R] each of the blue lines was the dominant, but now we would have to go deeper for both children to correctly update for the red line.

    → Reply
»
20 months ago, # |
  Vote: I like it +6 Vote: I do not like it

the first idea is that in a node you keep a function that cannot be maximal beyond the bounds of l, r

the second idea is that when executing a get request, you get the maximum value of all the functions from all the visited tree nodes on the way to the leaf, and because of this, you have to update only one subtree (in which current function is possible can dominate).

→ Reply
  • »
    »
    20 months ago, # ^ |
    ← Rev. 3   Vote: I like it +22 Vote: I do not like it

    Oh okay, i understand now. The second idea is what i was missing. Indeed, it is clear that taking the maximum out of all the nodes in the path from the root to the leaf would result in the max answer (i totally missed this part). Thank you!

    → Reply