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 formula_1 that accepts an array, a range query formula_2 on an array formula_3 takes two indices formula_4 and formula_5 and returns the result of formula_1 when applied to the subarray formula_7. For example, for a function formula_8 that returns the sum of all values in an array, the range query formula_9 returns the sum of all values in the range formula_10.
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: formula_11
This strategy may be extended to any other binary operation formula_1 whose inverse function formula_13 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 formula_14
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.
When the function of interest in a range query is a semigroup operator, the notion of formula_13 is not always defined, so the strategy in the previous section does not work. Andrew Yao showed that there exists an efficient solution for range queries that involve semigroup operators. He proved that for any constant c, a pre-processing of time and space formula_16 allows to answer range queries on lists where f is a semigroup operator in formula_17 time, where formula_18 is a certain functional inverse of the Ackermann function.
There are some semigroup operators that admit slightly better solutions. For instance when formula_19. Assume formula_20 then formula_21 returns the index of the minimum element of formula_22. Then formula_23 denotes the corresponding minimum range query. There are several data structures that allow to answer a range minimum query in formula_24 time using a pre-processing of time and space formula_25. One such solution is based on the equivalence between this problem and the lowest common ancestor problem.
The Cartesian tree formula_26 of an array formula_27 has as root formula_28 and as left and right subtrees the Cartesian tree of formula_29 and the Cartesian tree of formula_30 respectively. A range minimum query formula_23 is the lowest common ancestor in formula_26 of formula_33 and formula_34. Because the lowest common ancestor can be solved in constant time using a pre-processing of time and space formula_25, range minimum query can as well. The solution when formula_36 is analogous. Cartesian trees can be constructed in linear time.
Mode.
The mode of an array is the element that appears the most in it. For instance the mode of formula_37 is . In case of a tie, any of the most frequent elements might be picked as the mode. A range mode query consists in pre-processing formula_27 such that we can find the mode in any range of formula_27. Several data structures have been devised to solve this problem, we summarize some of the results in the following table.
Recently Jørgensen et al. proved a lower bound on the cell-probe model of formula_40 for any data structure that uses S cells.
Median.
This particular case is of special interest since finding the median has several applications. 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. However its generalization through range median queries is recent. A range median query formula_41 where "A,i" and "j" have the usual meanings returns the median element of formula_42. Equivalently, formula_41 should return the element of formula_42 of rank formula_45. Range median queries cannot be solved by following any of the previous methods discussed above including Yao's approach for semigroup operators.
There have been studied two variants of this problem, the offline version, where all the "k" queries of interest are given in a batch, and a version where all the pre-processing is done up front. The offline version can be solved with formula_46 time and formula_47 space.
The following pseudocode of the quickselect algorithm shows how to find the element of rank r in formula_42 an unsorted array of distinct elements, to find the range medians we set formula_49.
 rangeMedian(A, i, j, r) {
 if A.length() == 1
 return A[1]
 if A.low is undefined then
 m = median(A)
 A.low = [e in A | e ;= m]
 A.high = [e in A | e ; m ]
 calculate t the number of elements of A[i, j] that belong to A.low
 if r ;= t then
 return rangeMedian(A.low, i, j, r)
 else
 return rangeMedian(A.high, i, j, r-t)
Procedure partitions , using 's median, into two arrays and , where the former contains
the elements of that are less than or equal to the median and the latter the rest of the elements of . If we know that the number of elements of formula_42 that
end up in is and this number is bigger than then we should keep looking for the element of rank in ; otherwise we should look for the element of rank formula_51 in . To find t, it is enough to find the maximum index formula_52 such that formula_53 is in and the maximum index formula_54 such that formula_55
is in . Then formula_56. The total cost for any query, without considering the partitioning part, is formula_57 since at most formula_57 recursion calls are done and only a constant number of operations are performed in each of them (to get the value of t fractional cascading should be used).
If a linear algorithm to find the medians is used, the total cost of pre-processing for k range median queries is formula_59. The algorithm can also be modified to solve the online version of the problem.
Majority.
Finding frequent elements in a given set of items is one of the most important tasks in data mining. Finding frequent elements might be a difficult task to achieve when most items have similar frequencies. Therefore, it might be more beneficial if some threshold of significance was used for detecting such items. One of the most famous algorithms for finding the majority of an array was proposed by Boyer and Moore which is also known as the Boyer–Moore majority vote algorithm. Boyer and Moore proposed an algorithm to find the majority element of a string (if it has one) in formula_25 time and using formula_24 space. In the context of Boyer and Moore’s work and generally speaking, a majority element in a set of items (for example string or an array) is one whose number of instances is more than half of the size of that set. Few years later, Misra and Gries proposed a more general version of Boyer and Moore's algorithm using formula_62 comparisons to find all items in an array whose relative frequencies are greater than some threshold formula_63. A range formula_64-majority query is one that, given a subrange of a data structure (for example an array) of size formula_65, returns the set of all distinct items that appear more than (or in some publications equal to) formula_66 times in that given range. In different structures that support range formula_64-majority queries, formula_68 can be either static (specified during pre-processing) or dynamic (specified at query time). Many of such approaches are based on the fact that, regardless of the size of the range, for a given formula_64 there could be at most formula_70 distinct "candidates" with relative frequencies at least formula_64. By verifying each of these candidates in constant time, formula_70 query time is achieved. A range formula_64-majority query is decomposable in the sense that a formula_64-majority in a range formula_75 with partitions formula_76 and formula_77 must be a formula_64-majority in either formula_76or formula_77. Due to this decomposability, some data structures answer formula_64-majority queries on one-dimensional arrays by finding the Lowest common ancestor (LCA) of the endpoints of the query range in a Range tree and validating two sets of candidates (of size formula_70) from each endpoint to the lowest common ancestor in constant time resulting in formula_70 query time.
Two-dimensional arrays.
Gagie et al. proposed a data structure that supports range formula_64-majority queries on an formula_85 array formula_86. For each query formula_87 in this data structure a threshold formula_63 and a rectangular range formula_89 are specified, and the set of all elements that have relative frequencies (inside that rectangular range) greater than or equal to formula_64 are returned as the output. This data structure supports dynamic thresholds (specified at query time) and a pre-processing threshold formula_91 based on which it is constructed. During the pre-processing, a set of "vertical" and "horizontal" intervals are built on the formula_92 array. Together, a vertical and a horizontal interval form a "block." Each block is part of a "superblock" nine times bigger than itself (three times the size of the block's horizontal interval and three times the size of its vertical one). For each block a set of candidates (with formula_93 elements at most) is stored which consists of elements that have relative frequencies at least formula_94 (the pre-processing threshold as mentioned above) in its respective superblock. These elements are stored in non-increasing order according to their frequencies and it is easy to see that, any element that has a relative frequency at least formula_91 in a block must appear its set of candidates. Each formula_64-majority query is first answered by finding the "query block," or the biggest block that is contained in the provided query rectangle in formula_24 time. For the obtained query block, the first formula_98 candidates are returned (without being verified) in formula_70 time, so this process might return some false positives. Many other data structures (as discussed below) have proposed methods for verifying each candidate in constant time and thus maintaining the formula_70 query time while returning no false positives. The cases in which the query block is smaller than formula_101 are handled by storing formula_102 different instances of this data structure of the following form:
formula_103
where formula_104 is the pre-processing threshold of the formula_105-th instance. Thus, for query blocks smaller than formula_101 the formula_107-th instance is queried. As mentioned above, this data structure has query time formula_70 and requires formula_109 bits of space by storing a Huffman-encoded copy of it (note the formula_110 factor and also see Huffman coding).
One-dimensional arrays.
Chan et al. proposed a data structure that given a one-dimensional arrayformula_86, a subrange formula_75 of formula_86 (specified at query time) and a threshold formula_64 (specified at query time), is able to return the list of all formula_64-majorities in formula_70 time requiring formula_117 words of space. To answer such queries, Chan et al. begin by noting that there exists a data structure capable of returning the "top-k" most frequent items in a range in formula_118 time requiring formula_25 words of space. For a one-dimensional array formula_120, let a one-sided top-k range query to be of form formula_121. For a maximal range of ranges formula_122 in which the frequency of a distinct element formula_123 in formula_86 remains unchanged (and equal to formula_1), a horizontal line segment is constructed. The formula_126-interval of this line segment corresponds to formula_127 and it has a formula_128-value equal to formula_1. Since adding each element to formula_86 changes the frequency of exactly one distinct element, the aforementioned process creates formula_25 line segments. Moreover, for a vertical line formula_132 all horizonal line segments intersecting it are sorted according to their frequencies. Note that, each horizontal line segment with formula_126-interval formula_134 corresponds to exactly one distinct element formula_123 in formula_86, such that formula_137. A top-k query can then be answered by shooting a vertical ray formula_132 and reporting the first formula_139 horizontal line segments that intersect it (remember from above that these line segments are already sorted according to their frequencies) in formula_118 time.
Chan et al. first construct a range tree in which each branching node stores one copy of the data structure described above