Noble_Mushtak's blog

Alternate Implementation of Li Chao Tree?
By Noble_Mushtak, history, 21 month(s) ago, In English

I recently found an implementation of Li Chao tree in this ICPC notebook, and it is quite different than the implementations I have seen before. Usually, I see the insert_line method implemented in a way similar to that described in this cp-algorithms.com article, where you recur either on the left child or the right child depending on if the new line is above or below the current line at the midpoint of the interval. However in this implementation, they recur on both the left and the right child, but they stop recurring once the new line is completely below or completely above the current line in that node.

Does this implementation still handle inserting lines in $$$O(\log n)$$$ time in the worst case? I tried using this implementation on the Frog 3 problem on AtCoder and it got AC, but I am wondering if it is due to weak test cases, or if this implementation is actually valid and really handles inserting lines in $$$O(\log n)$$$ time. I wasn't able to find a counterexample where inserting a line would cause the implementation to traverse the whole tree, but recurring on both the left and the right children seems strange to me.

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Noble_Mushtak (previous revision, new revision, compare).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

I think you probably want a combination of both implementations, that is, only going to one subtree and pruning some recursion calls by checking if the current line is always above/below.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Also, it probably is hard to construct bad cases for the ICPC notebook code. It only recursively goes down if it intersects the current line at (l, r).

    → Reply
»
21 month(s) ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

[redacted]

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

I think you should be able to conceive a counter-example if you insert a bunch of lines such that the line on node with range $$$l..r$$$ passes through $$$0$$$ at some $$$x \in (l,r)$$$. Then inserting line $$$y=0$$$ multiple times should break the complexity.

You should theoretically be able to fill the tree with such lines in pre-order (it may be hard with integer slopes). It’s definitely much easier if the DS must support insertion of segments (line on range $$$x_1..x_2$$$). So, at least for insertion of segments, it can degenerate to linear complexity for insertion. Maybe someone can give an example that breaks with (unbounded) lines.

→ Reply