Range query (computer science)
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 that accepts an array, a range query on an array takes two indices and and returns the result of when applied to the subarray. For example, for a function that returns the sum of all values in an array, the range query returns the sum of all values in the range.Solutions
Prefix sum array
Range sum queries may be answered in constant time and linear space by pre-computing an array of same length as the input such that for every index, the element is the sum of the first elements of. Any query may then be computed as follows:This strategy may be extended to any other binary operation whose inverse function is well-defined and easily computable. It can also be extended to higher dimensions with a similar pre-processing. For example, if contains the sum of the first elements of, then
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 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, a pre-processing of time and space allows to answer range queries on lists where is a semigroup operator in time, where is a certain functional inverse of the Ackermann function.There are some semigroup operators that admit slightly better solutions. For instance when. Assume then returns the index of the minimum element of. Then denotes the corresponding minimum range query. There are several data structures that allow to answer a range minimum query in time using a pre-processing of time and space. One such solution is based on the equivalence between this problem and the lowest common ancestor problem.
The Cartesian tree of an array has as root and as left and right subtrees the Cartesian tree of and the Cartesian tree of respectively. A range minimum query is the lowest common ancestor in of and. Because the lowest common ancestor can be solved in constant time using a pre-processing of time and space, range minimum query can as well. The solution when 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 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 such that we can find the mode in any range of. Several data structures have been devised to solve this problem, we summarize some of the results in the following table.| Space | Query Time | Restrictions |
Recently Jørgensen et al. proved a lower bound on the cell-probe model of for any data structure that uses 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, using the median of medians algorithm. However its generalization through range median queries is recent. A range median query where A,i and j have the usual meanings returns the median element of. Equivalently, should return the element of of rank. 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 time and space.
The following pseudocode of the quickselect algorithm shows how to find the element of rank in an unsorted array of distinct elements, to find the range medians we set.
rangeMedian
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 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 in. To find, it is enough to find the maximum index such that is in and the maximum index such that
is in. Then. The total cost for any query, without considering the partitioning part, is since at most recursion calls are done and only a constant number of operations are performed in each of them.
If a linear algorithm to find the medians is used, the total cost of pre-processing for range median queries is. 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 in time and using space. In the context of Boyer and Moore's work and generally speaking, a majority element in a set of items 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 comparisons to find all items in an array whose relative frequencies are greater than some threshold. A range -majority query is one that, given a subrange of a data structure of size, returns the set of all distinct items that appear more than times in that given range. In different structures that support range -majority queries, can be either static or dynamic. Many of such approaches are based on the fact that, regardless of the size of the range, for a given there could be at most distinct candidates with relative frequencies at least. By verifying each of these candidates in constant time, query time is achieved. A range -majority query is decomposable in the sense that a -majority in a range with partitions and must be a -majority in either or. Due to this decomposability, some data structures answer -majority queries on one-dimensional arrays by finding the Lowest common ancestor of the endpoints of the query range in a Range tree and validating two sets of candidates from each endpoint to the lowest common ancestor in constant time resulting in query time.Two-dimensional arrays
Gagie et al. proposed a data structure that supports range -majority queries on an array. For each query in this data structure a threshold and a rectangular range are specified, and the set of all elements that have relative frequencies greater than or equal to are returned as the output. This data structure supports dynamic thresholds and a pre-processing threshold based on which it is constructed. During the pre-processing, a set of vertical and horizontal intervals are built on the array. Together, a vertical and a horizontal interval form a block. Each block is part of a superblock nine times bigger than itself. For each block a set of candidates is stored which consists of elements that have relative frequencies at least 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 in a block must appear its set of candidates. Each -majority query is first answered by finding the query block, or the biggest block that is contained in the provided query rectangle in time. For the obtained query block, the first candidates are returned in time, so this process might return some false positives. Many other data structures have proposed methods for verifying each candidate in constant time and thus maintaining the query time while returning no false positives. The cases in which the query block is smaller than are handled by storing different instances of this data structure of the following form:where is the pre-processing threshold of the -th instance. Thus, for query blocks smaller than the -th instance is queried. As mentioned above, this data structure has query time and requires bits of space by storing a Huffman-encoded copy of it.
One-dimensional arrays
Chan et al. proposed a data structure that given a one-dimensional array, a subrange of and a threshold , is able to return the list of all -majorities in time requiring 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 time requiring words of space. For a one-dimensional array, let a one-sided top-k range query to be of form. For a maximal range of ranges in which the frequency of a distinct element in remains unchanged, a horizontal line segment is constructed. The -interval of this line segment corresponds to and it has a -value equal to. Since adding each element to changes the frequency of exactly one distinct element, the aforementioned process creates line segments. Moreover, for a vertical line all horizontal line segments intersecting it are sorted according to their frequencies. Note that, each horizontal line segment with -interval corresponds to exactly one distinct element in, such that. A top-k query can then be answered by shooting a vertical ray and reporting the first horizontal line segments that intersect it in time.Chan et al. first construct a range tree in which each branching node stores one copy of the data structure described above for one-sided range top-k queries and each leaf represents an element from. The top-k data structure at each node is constructed based on the values existing in the subtrees of that node and is meant to answer one-sided range top-k queries. Please note that for a one-dimensional array, a range tree can be constructed by dividing into two halves and recursing on both halves; therefore, each node of the resulting range tree represents a range. It can also be seen that this range tree requires words of space, because there are levels and each level has nodes. Moreover, since at each level of a range tree all nodes have a total of elements of at their subtrees and since there are levels, the space complexity of this range tree is.
Using this structure, a range -majority query on with is answered as follows. First, the lowest common ancestor of leaf nodes and is found in constant time. Note that there exists a data structure requiring bits of space that is capable of answering the LCA queries in time. Let denote the LCA of and, using and according to the decomposability of range -majority queries, the two-sided range query can be converted into two one-sided range top-k queries. These two one-sided range top-k queries return the top- most frequent elements in each of their respective ranges in time. These frequent elements make up the set of candidates for -majorities in in which there are candidates some of which might be false positives. Each candidate is then assessed in constant time using a linear-space data structure that is able to determine in time whether or not a given subrange of an array contains at least instances of a particular element.