Content deleted Content added
→Median: add link to quickselect |
m Open access bot: arxiv added to citation with #oabot. |
||
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|first=Danny|last=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|last=Meng|first=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==
| |||