You store the envelope as a list of lines sorted by slope. You also store breakpoints: values where adjacent lines intersect. To query at , binary search for the largest breakpoint . The line that becomes optimal past that breakpoint gives you the minimum.
This works because when you sort lines by slope, their pairwise intersections fall at increasing positions. Your breakpoints are sorted, so binary search finds the correct segment in . Building takes if slopes are pre-sorted; queries take total. That beats the naive approach.