Range query (computer science): Difference between revisions

Revision as of 15:14, 14 January 2024

Revision as of 18:07, 18 January 2024

Line 12:

{{Main|Prefix sum}}

Range sum queries may be answered in [[constant time]] and [[space complexity|linear space]] by pre-computing an array {{mvar|p}} of same length as the input such that for every index {{mvar|i}}, the element {{mvar|p<mathsub>p_ii</mathsub>}} is the sum of the first {{mvar|i}} elements of {{mvar|a}}. Any query may then be computed as follows: <math display="block">\operatorname{sum}_q(l, r) = p_r - p_{l-1}.</math>

This strategy may be extended to any other [[binary operation]] <math>f</math> whose [[inverse function]] <math>f^{-1}</math> is well-defined and easily computable.<ref name="morin">{{cite journal|first1=Danny|last1=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|bibcode=2003cs........7034K }}</ref> It can also be extended to two-dimensionalhigher arraysdimensions with a similar pre-processing.<ref name=menhe>{{cite journal|last1=Meng|first1=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|arxiv=1106.5076 }}</ref> For example, if {{mvar|p_i,j}} contains the sum of the first {{math|''i'' &times; ''j''}} elements of {{mvar|a}}, then <math display="block">\operatorname{sum}_q(l, r, t, b) = p_{r,b} - p_{l-1,b} - p_{r, t-1} + p_{l-1,t-1}.</math>

===Dynamic range queries===