Alternate Implementation of Li Chao Tree?

Revision en3, by Noble_Mushtak, 2022-07-31 03:56:30

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.

Tags #convex hull trick, #li chao tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Noble_Mushtak 2022-07-31 03:56:30 20 (published)
en2 English Noble_Mushtak 2022-07-31 03:55:43 4
en1 English Noble_Mushtak 2022-07-31 03:55:30 1394 Initial revision (saved to drafts)