# Pre-computing min/max for interval queries?

I'm basically trying to figure out if the following problem has a common name and/or a standard solution in computer science.

Let assume we're given $$N$$ two-dimensional tuples $$(x_i, y_i)$$. This data is fixed/static and we want to pre-compute a data structure that allows to run interval queries returning the max or min w.r.t. $$y$$ in the specified $$x$$ interval. For instance, for a given interval $$[x_{lower}, x_{upper}]$$ the query should return the min or max $$y_i$$ for all tuples satisfying $$x_{lower} \leq x_i \leq x_{upper}$$.

The obvious solutions are:

• A naive linear scan, which would have a complexity of $$O(N)$$.

• A brute-force pre-computing solution would pre-compute the min/max for all possible $$[x_{lower}, x_{upper}]$$ pairs, which would have $$O(N^2)$$ in terms of runtime and memory complexity.

It feels like there should be a smart solution achieving sub-linear query complexity without the $$O(N^2)$$ complexity of a brute-force pre-computation?

One simple approach would be to store the tuples in a balanced binary search tree, using $$x$$ as the key. Augment that data structure to store in each node the maximum and minimum value of $$y$$, among all tuples that are stored in the subtree rooted at that node. You can construct such a data structure in $$O(N \log N)$$ time (preprocessing). Once you've done so, this data structure will allow you to answer interval queries in $$O(\log N)$$ time. If you also want to support interval queries on $$y$$, make a second tree, this one using $$y$$ as the key.