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:
Sorted queries: If values are monotonic (say, increasing), the optimal line also moves monotonically. Use a deque (double-ended queue that supports push/pop from both ends): amortized per query.
Arbitrary queries: Use binary search on the envelope or a Li Chao tree. per query. I'll focus on sorted queries first. That's the cleanest case.