One-Dimensional Range Queries

There are n hotels on the Strip, H1 ... Hn. Every day, many people call and ask for the cheapest Strip hotel within walking distance of some particular point of interest, and each person has a personal idea of what "walking distance" means.
You want to design an algorithm and data structure to handle these queries. You will update your data structure at the beginning of each business day, as you enter the room rates for that day. You will translate each query into an interval [i,j], and return the cheapest hotel in the sublist Hi ... Hj. Call this query Q[i,j].
Your requirements are as follows:
1. Your data structure will not be too large.
2. You want to be able to answer each query fast.
Clearly, there is a trade-off between the two complexity measures, so there is no obvious definition of the "best" solution. But if we know how many queries there will be in a day, and also how much time it takes to construct a data structure of a given size, we can minimize total time.

The query could be for something other than minimum; for example, Q[i,j] could the sum of the numbers xi + ... + xi. Or, instead of minimum or sum, use any associative operation.
If you use sum, you can achieve O(1) time for a query with a data structure of size O(n), by using subtraction. But this is "cheating," because your associative operation may not have inverses.