Range query (computer science): Difference between revisions

Revision as of 19:05, 13 January 2021

Revision as of 00:27, 26 March 2021

Line 10:

For example, for <math>f = \sum</math> and <math>A[1,n]</math> an array of numbers, the range query <math>\sum_{i,j} A</math> computes <math>\sum A[i,j] = (a_i+\ldots + a_j)</math>, for any <math>1 \leq i \leq j \leq n</math>. These queries may be answered in [[constant time]] and using <math>O(n)</math> extra space by calculating the sums of the first {{mvar|i}} elements of {{mvar|A}} and storing them into an auxiliary array {{mvar|B}}, such that <math>B[i]</math> contains the sum of the first {{mvar|i}} elements of {{mvar|A}} for every <math>0\leq i\leq n</math>. Therefore, any query might be answered by doing <math>\sum A[i,j] = B[j] - B[i-1]</math>.

This strategy may be extended for every [[Group (mathematics)|group]] operator {{mvar|f}} where the notion of <math>f^{-1}</math> is well defined and easily computable.<ref name="morin">{{cite journal|firstfirst1=Danny|lastlast1=Krizanc|first2=Pat|last2=Morin|author2-link= Pat Morin |first3=Michiel H. M.|last3=Smid|title=Range Mode and Range Median Queries on Lists and Trees|journal=ISAAC|year=2003|pages=517–526|url=http://cg.scs.carleton.ca/~morin/publications/|arxiv=cs/0307034}}</ref> Finally, this solution can be extended to two-dimensional arrays with a similar preprocessing.<ref name=menhe>{{cite journal|lastlast1=Meng|firstfirst1=He|first2=J. Ian|last2=Munro|first3=Patrick K.|last3=Nicholson|title=Dynamic Range Selection in Linear Space|journal=ISAAC|year=2011|pages=160–169}}</ref>

==Examples==

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=eE 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_k</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.

Line 41:

|}

Recently Jørgensen et al. proved a lower bound on the [[cell-probe model]] of <math>\Omega\left(\tfrac{\log n}{\log (S w/n)}\right)</math> for any data structure that uses {{mvar|S}} cells.<ref name=jorgensen>{{cite journal|lastlast1=Greve|firstfirst1=M|last2=J{\o}rgensen|first2= A.|last3=Larsen|first3= K.|last4=Truelsen|first4= J.|title=Cell probe lower bounds and approximations for range mode|journal=Automata, Languages and Programming|year=2010|pages=605–616}}</ref>

===Median===

This particular case is of special interest since finding the [[median]] has several applications.<ref name=heriel>{{cite journal|firstfirst1=Sariel|lastlast1=Har-Peled|author1-link=Sariel Har-Peled|first2=S.|last2=Muthukrishnan|title=Range Medians|journal=ESA|year=2008|pages=503–514}}</ref> On the other hand, the median problem, a special case of the [[selection problem]], is solvable in ''O''(''n''), using the [[median of medians]] algorithm.<ref name=tarjanmedian>{{Cite journal | last1 = Blum | first1 = M. | authorlink1 = Manuel Blum| last2 = Floyd | first2 = R. W. | authorlink2 = Robert Floyd| last3 = Pratt | first3 = V. R. | authorlink3 = Vaughan Pratt| last4 = Rivest | first4 = R. L. | authorlink4 = Ron Rivest| last5 = Tarjan | first5 = R. E. | authorlink5 = Robert Tarjan | title = Time bounds for selection | doi = 10.1016/S0022-0000(73)80033-9 | journal = Journal of Computer and System Sciences | volume = 7 | issue = 4 | pages = 448–461 | date =August 1973 | url = http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf| ref = harv }}</ref> However its generalization through range median queries is recent.<ref name=ethpaper /> A range median query <math>\operatorname{median}(A,i,j)</math> where ''A,i'' and ''j'' have the usual meanings returns the median element of <math>A[i,j]</math>. Equivalently, <math>\operatorname{median}(A,i,j)</math> should return the element of <math>A[i,j]</math> of rank <math>\frac{j-i}{2}</math>. Range median queries cannot be solved by following any of the previous methods discussed above including Yao's approach for semigroup operators.<ref name="morin kranakis" />

There have been studied two variants of this problem, the [[offline algorithm|offline]] version, where all the ''k'' queries of interest are given in a batch, and a version where all the preprocessing is done up front. The offline version can be solved with <math>O(n\log k + k \log n)</math> time and <math>O(n\log k)</math> space.

The following pseudocode of the [[Quickselect|quickselect algorithm]] shows how to find the element of rank {{mvar|r}} in <math>A[i,j]</math> an unsorted array of distinct elements, to find the range medians we set <math>r=\frac{j-i}{2}</math>.<ref name="ethpaper">{{cite journal|lastlast1=Beat|firstfirst1=Gfeller|first2=Peter|last2=Sanders|author2-link=Peter Sanders (computer scientist)|title=Towards Optimal Range Medians|journal=ICALPIcalp (1)|year=2009|pages=475–486}}</ref>

rangeMedian(A, i, j, r) {

Line 75:

==Related problems==

All the problems described above have been studied for higher dimensions as well as their dynamic versions. On the other hand, range queries might be extended to other data structures like [[Tree (data structure)|trees]],<ref name="morin kranakis">{{cite journal|first1=P|last1=Bose|author1-link=Jit Bose|first2=E.|last2=Kranakis|first3=P.|last3=Morin|author3-link= Pat Morin |first4=Y.|last4=Tang|title=Approximate range mode and range median queries|journal=In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS 2005), volumeVolume 3404 of Lecture Notes in ComputerScience|year=2005|pages=377–388|url=http://cg.scs.carleton.ca/~morin/publications/}}</ref> such as the [[level ancestor problem]]. A similar family of problems are [[Range searching|orthogonal range]] queries, also known as counting queries.

== See also ==