In data structures, a range query consists of preprocessing some input data into a data structure to efficiently answer any number of queries on any subset of the input. Particularly, there is a group of problems that have been extensively studied where the input is an array of unsorted numbers and a query consists of computing some function, such as the minimum, on a specific range of the array.
Definition
A range query on an array of n elements of some set, denoted, takes two indices, a function defined over arrays of elements of and outputs. For example, for and an array of numbers, the range query computes, for any. These queries may be answered in constant time and using extra space by calculating the sums of the first elements of and storing them into an auxiliary array, such that contains the sum of the first elements of for every . Therefore, any query might be answered by doing. This strategy may be extended for every group operator where the notion of is well defined and easily computable. Finally, this solution can be extended to two-dimensional arrays with a similar preprocessing.
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 preprocessing 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 preprocessing 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 preprocessing 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 A is the element that appears the most in A. For instance the mode of is. In case of ties any of the most frequent elements might be picked as mode. A range mode query consists in preprocessing 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.
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 preprocessing is done up front. The offline version can be solved with time and space. The following pseudo code 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 preprocessing for range median queries is. The algorithm can also be modified to solve the online version of the problem.
Related problems
All the problems described above have been studied for higher dimensions as well as their dynamic versions. On the other hand, range queries might be extended to other data structures like trees, such as the level ancestor problem. A similar family of problems are orthogonal range queries, also known as counting queries.
