A Li Chao tree is a segment tree over the range of possible values. Each node stores one line. Insert: Compare new line with stored line at the midpoint.
Keep the one that wins at midpoint. Recurse with the other line to the half where it might win. Query: Walk from root to leaf at . Return the best value seen. Both operations: . Works for arbitrary slopes and arbitrary queries. It's the most general CHT data structure.