
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.
-
For example you could store the answer to Q[i,j] for all i and j.
Then each query could be answered in O(1) time, but your data structure
would have quadratic size.
-
At the other extreme, you could simply store the answer to Q[i,i] for all i.
Then each query could be answered in O(n) time.
-
Both of the above are probably "bad"; the first because it requires too
much storage, and the second because it takes too much time to answer a
query.
-
How about storing Q[i,i] for all i, and also storing Q[i+1,i+10] for
all i which are multiples of 10? How big is your data structure, and
how long would it take to answer a query?
-
How about picking a subset I of "demarcation" indices. Then, store
Q[i+1,j] for all i < j such that one of the following holds:
-
Both i and j are members of I.
-
There is no member of I between i and j, although either i or j can be
a member of I.
What would you pick for your set of demarcation values? All multiples of 10?
Suppose you did.
Then, for example, the query Q[14,87] could be answered by taking the
minimum of Q[14,20], Q[21,80], and Q[81,87].
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.
