I recently found an implementation of Li Chao tree [in this ICPC notebook](https://github.com/imeplusplus/icpc-notebook/blob/master/data-structures/ita_lichao.cpp), 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](https://cp-algorithms.com/geometry/convex_hull_trick.html#li-chao-tree), 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](https://atcoder.jp/contests/dp/submissions/33645641) 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.
↵
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](https://atcoder.jp/contests/dp/submissions/33645641) 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.
