1
$\begingroup$

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?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks! I noticed that my mistake was to search for "interval query" instead of "range query". This term has revealed an relationship to range minimum queries and segment trees, which seem to be very similar to what you are suggesting. $\endgroup$
    – AlexN
    Oct 26, 2021 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.