Li Chao tree: segment tree over x-values. Each node stores the line that's best at the midpoint of its range. Insert line : compare with current line at midpoint.
The winner stays. The loser might still be optimal in some child. Recurse into the half where the loser could win. At most nodes visited per insert. Query x: traverse from root to leaf for x. At each node, evaluate the stored line. Return the minimum across all nodes on the path.