Range query (computer science): Difference between revisions

Revision as of 09:35, 6 July 2021

Revision as of 21:14, 16 August 2021

Line 18:

{{main|Range minimum query}}

When the function of interest in a range query is a [[semigroup]] operator, the notion of <math>f^{-1}</math> is not always defined, so the strategy in the previous section does not work. [[Andrew Yao]] showed<ref name="yao">{{cite journal|last=Yao, A. C|title=Space-Time Tradeoff for Answering Range Queries|journal=E 14th Annual ACM Symposium on the Theory of Computing|year=1982|pages=128–136}}</ref> that there exists an efficient solution for range queries that involve semigroup operators. He proved that for any constant {{mvar|c}}, a preprocessing of time and space <math>\theta(c\cdot n)</math> allows to answer range queries on lists where {{mvar|f}} is a semigroup operator in <math>\theta(\alpha_c(n))</math> time, where <math>\alpha_kalpha_c</math> is a certain functional inverse of the [[Ackermann function]].

There are some semigroup operators that admit slightly better solutions. For instance when <math>f\in \{\max,\min\}</math>. Assume <math> f = \min</math> then <math>\min(A[1..n])</math> returns the index of the [[minimum]] element of <math>A[1..n]</math>. Then <math>\min_{i,j}(A)</math> denotes the corresponding minimum range query. There are several data structures that allow to answer a range minimum query in <math>O(1)</math> time using a preprocessing of time and space <math>O(n)</math>. One such solution is based on the equivalence between this problem and the [[lowest common ancestor]] problem.