Content deleted Content added
→Definition: make less formal and easier to understand |
m mislink |
||
Line 8:
Given a [[function (programming)|function]] <math>f</math> that accepts an array, a range query <math>f_q(l, r)</math> on an array <math>a=[a_1,..,a_n]</math> takes two indices <math>l</math> and <math>r</math> and returns the result of <math>f</math> when applied to the subarray <math>[a_l, \ldots, a_r]</math>. For example, for a function <math>\operatorname{sum}</math> that returns the sum of all values in an array, the range query <math>\operatorname{sum}_q(l, r)</math> returns the sum of all values in the range <math>[l, r]</math>.
Range sum queries may be answered in [[constant time]] and [[space complexity|linear 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|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> Finally, this solution can be extended to two-dimensional arrays 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>
| |||