Store the envelope as a list of lines sorted by slope. Also store breakpoints: values where adjacent lines intersect. To query at : binary search for the largest breakpoint . The line after that breakpoint is optimal.
This works because the envelope is convex. The breakpoints are sorted. Binary search finds the correct segment in . Total: for building the envelope (if slopes sorted), for n queries. Still much better than .