In computer science, the range query problem consists of efficiently answering several queries regarding a given interval of elements within an array. For example, a common task, known as range minimum query, is finding the smallest value inside a given range within a list of numbers.
Definition Given a function f {\displaystyle f} that accepts an array, a range query f q ( l , r ) {\displaystyle f_{q}(l,r)} on an array a = [ a 1 , . . , a n ] {\displaystyle a=[a_{1},..,a_{n}]} takes two indices l {\displaystyle l} and r {\displaystyle r} and returns the result of f {\displaystyle f} when applied to the subarray [ a l , … , a r ] {\displaystyle [a_{l},\ldots ,a_{r}]} . For example, for a function sum {\displaystyle \operatorname {sum} } that returns the sum of all values in an array, the range query sum q ( l , r ) {\displaystyle \operatorname {sum} _{q}(l,r)} returns the sum of all values in the range [ l , r ] {\displaystyle [l,r]} .
Solutions
Prefix sum array
Range sum queries may be answered in constant time and linear space by pre-computing an array p of same length as the input such that for every index i, the element pi is the sum of the first i elements of a. Any query may then be computed as follows: sum q ( l , r ) = p r − p l − 1 . {\displaystyle \operatorname {sum} _{q}(l,r)=p_{r}-p_{l-1}.}
This strategy may be extended to any other binary operation f {\displaystyle f} whose inverse function f − 1 {\displaystyle f^{-1}} is well-defined and easily computable. It can also be extended to higher dimensions with a similar pre-processing. For example, if pi,j contains the sum of the first i × j elements of a, then sum q ( l , r , t , b ) = p r , b − p l − 1 , b − p r , t − 1 + p l − 1 , t − 1 . {\displaystyle \operatorname {sum} _{q}(l,r,t,b)=p_{r,b}-p_{l-1,b}-p_{r,t-1}+p_{l-1,t-1}.}
Dynamic range queries A more difficult subset of the problem consists of executing range queries on dynamic data; that is, data that may mutate between each query. In order to efficiently update array values, more sophisticated data structures like the segment tree or Fenwick tree are necessary.
Examples
Semigroup operators
… excerpt ends here. Continue reading the full article.
