What Is the Convex Hull Trick?

The Convex Hull Trick maintains the lower envelope as you add lines. For each query, it finds the optimal line on the envelope. Two cases:

$1.$ Sorted queries: If $x_i$ values are monotonic (say, increasing), the optimal line also moves monotonically. Use a deque (double-ended queue that supports push/pop from both ends): $O(1)$ amortized per query.

$2.$ Arbitrary queries: Use binary search on the envelope or a Li Chao tree. $O(\log n)$ per query. I'll focus on sorted queries first. That's the cleanest case.