# Range query (data structures)

(Redirected from Range Queries)

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 on a specific range of the array. In this article we describe some of these problems together with their solutions.

## Problem statement

We may state the problem of range queries in the following way: a range query ${\displaystyle q_{f}(A,i,j)}$ on an array ${\displaystyle A=[a_{1},a_{2},..,a_{n}]}$ of n elements of some set ${\displaystyle S}$, denoted ${\displaystyle A[1,n]}$, takes two indices ${\displaystyle 1\leq i\leq j\leq n}$, a function ${\displaystyle f}$ defined over arrays of elements of ${\displaystyle S}$ and outputs ${\displaystyle f(A[i,j])=f(a_{i},\ldots ,a_{j})}$. This should be done space and time efficient.

Consider for instance ${\displaystyle f=sum}$ and ${\displaystyle A[1,n]}$ an array of numbers, the range query ${\displaystyle sum(A,i,j)}$ computes ${\displaystyle sum(A[i,j])=(a_{i}+\ldots +a_{j})}$, for any ${\displaystyle 1\leq i\leq j\leq n}$. These queries may be answered in constant time and using ${\displaystyle O(n)}$ extra space by calculating the sums of the first ${\displaystyle i}$ elements of ${\displaystyle A}$ and storing them into an auxiliary array ${\displaystyle B}$, such that ${\displaystyle B[i]}$ contains the sum of the first ${\displaystyle i}$ elements of ${\displaystyle A}$ for every ${\displaystyle 0\leq i\leq n}$.Therefore any query might be answered by doing ${\displaystyle sum(A[i,j])=B[j]-B[i-1]}$.

This strategy may be extended for every group operator ${\displaystyle f}$ where the notion of ${\displaystyle f^{-1}}$ is well defined and easily computable.[1] Finally notice this solution might be extended for arrays of dimension two with a similar preprocessing.[2]

## Examples

### Semigroup operators

When the function of interest in a range query is a semigroup operator the notion of ${\displaystyle f^{-1}}$ is not always defined, therefore we can not use an analogous strategy to the previous section. Yao showed[3] that there exists an efficient solution for range queries that involve semigroup operators. He proved that for any constant ${\displaystyle c}$, a preprocessing of time and space ${\displaystyle \theta (c\cdot n)}$ allows to answer range queries on lists where ${\displaystyle f}$ is a semigroup operator in ${\displaystyle \theta (\alpha _{c}(n))}$ time, where ${\displaystyle \alpha _{k}}$ is a certain functional inverse of the Ackermann function.

There are some semigroup operators that admit slightly better solutions. For instance when ${\displaystyle f\in \{\max ,\min \}}$. Assume ${\displaystyle f=\min }$ then ${\displaystyle \min(A[1..n])}$ returns the index of the minimum element of ${\displaystyle A[1..n]}$. Then ${\displaystyle \min(A,i,j)}$ denotes the corresponding minimum range query. There are several data structures that allow to answer a range minimum query in ${\displaystyle O(1)}$ time using a preprocessing of time and space ${\displaystyle O(n)}$. Probably the simplest solution to sketch here is based on the equivalence between this problem and the Lowest common ancestor problem. We briefly describe this solution.

The cartesian tree ${\displaystyle T_{A}}$ of an array ${\displaystyle A[1,n]}$ has as root ${\displaystyle a_{i}=min\{a_{1},a_{2},\ldots ,a_{n}\}}$ and it has as left and right subtrees the cartesian tree of ${\displaystyle A[1,i-1]}$ and the cartesian tree of ${\displaystyle A[i+1,n]}$ respectively. It is easy to see that a range minimum query ${\displaystyle min(A,i,j)}$ is the lowest common ancestor in ${\displaystyle T_{A}}$ of ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$. Since the lowest common ancestor is solvable in constant time using a preprocessing of time and space ${\displaystyle O(n)}$ thus so does the range minimum query problem. The solution when f = max 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 ${\displaystyle A=[4,5,6,7,4,]}$ is 4. In case of ties any of the most frequent elements might be picked as mode. A range mode query consists in preprocessing ${\displaystyle A[1,n]}$ such that we can find the mode in any range of ${\displaystyle A[1,n]}$. Several data structures have been devised to solve this problem, we summarize some of the results in the following table.[1]

Range Mode Queries
Space Query Time Restrictions
${\displaystyle O(n^{2-2\epsilon })}$ ${\displaystyle O(n^{\epsilon }\log n)}$ ${\displaystyle 0\leq \epsilon \leq 1/2}$
${\displaystyle O(n^{2}\log \log n/\log n)}$ ${\displaystyle O(1)}$

Recently Jørgensen et al. proved a lower bound on the cell probe model of ${\displaystyle \Omega \left({\frac {\log n}{\log(Sw/n)}}\right)}$ for any data structure that uses ${\displaystyle S}$ cells.[4]

### Median

This particular case is of special interest since finding the median has several applications, for further reference see.[5] On the other hand, the median problem, a special case of the selection problem, is solvable in O(n), by the median of medians algorithm.[6] However its generalization through range median queries is recent.[7] A range median query ${\displaystyle median(A,i,j)}$ where A,i and j have the usual meanings returns the median element of ${\displaystyle A[i,j]}$. Equivalently, ${\displaystyle median(A,i,j)}$ should return the element of ${\displaystyle A[i,j]}$ of rank ${\displaystyle {\frac {j-i}{2}}}$. Note that range median queries can not be solved by following any of the previous methods discussed above including Yao's approach for semigroup operators.[8]

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 we are interested in reduce the total cost and a version where all the preprocessing is done up front and we are interested in optimize the cost of any subsequent single query. Concerning the first variant of the problem recently was proven that can be solved in time ${\displaystyle O(n\log k+k\log n)}$ and space ${\displaystyle O(n\log k)}$. We describe such a solution.[7]

The following pseudo code shows how to find the element of rank ${\displaystyle r}$ in ${\displaystyle A[i,j]}$ an unsorted array of distinct elements, to find the range medians we set ${\displaystyle r={\frac {j-i}{2}}}$.

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 return rangeMedian(A.low, i,j,r)
else return rangeMedian(A.high, i,j, r-t)
}

Procedure rangeMedian partitions A, using A's median, into two arrays A.low and A.high, where the former contains the elements of A that are less than or equal to the median m and the latter the rest of the elements of A. If we know that the number of elements of ${\displaystyle A[i,j]}$ that end up in A.low is t and this number is bigger than r then we should keep looking for the element of rank r in A.low else we should look for the element of rank ${\displaystyle (r-t)}$ in A.high. To find ${\displaystyle t}$, it is enough to find the maximum index ${\displaystyle m\leq i-1}$ such that ${\displaystyle a_{m}}$ is in A.low and the maximum index ${\displaystyle l\leq j}$ such that ${\displaystyle a_{l}}$ is in A.high. Then ${\displaystyle t=l-m}$. The total cost for any query, without considering the partitioning part, is ${\displaystyle \log n}$ since at most ${\displaystyle \log n}$ recursion calls are done and only a constant number of operations are performed in each of them (to get the value of ${\displaystyle t}$ fractional cascading should be used). If a linear algorithm to find the medians is used, the total cost of preprocessing for ${\displaystyle k}$ range median queries is ${\displaystyle n\log k}$. Clearly this algorithm can be easily modified to solve the up front version of the problem.[7]

## 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,[8] such as the level ancestor problem. A similar family of problems are orthogonal range queries also known as counting queries.

## References

1. ^ a b Krizanc, Danny; Morin, Pat; Smid, Michiel H. M. (2003). "Range Mode and Range Median Queries on Lists and Trees". ISAAC: 517–526.
2. ^ Meng, He; Munro, J. Ian; Nicholson, Patrick K. (2011). "Dynamic Range Selection in Linear Space". ISAAC: 160–169.
3. ^ Yao, A. C (1982). "Space-Time Tradeoﬀ for Answering Range Queries". e 14th Annual ACM Symposium on the Theory of Computing: 128–136.
4. ^ Greve, M; J{\o}rgensen, A.; Larsen, K.; Truelsen, J. (2010). "Cell probe lower bounds and approximations for range mode". Automata, Languages and Programming: 605–616.
5. ^ Har-Peled, Sariel; Muthukrishnan, S. (2008). "Range Medians". ESA: 503–514.
6. ^ Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (August 1973). "Time bounds for selection" (PDF). Journal of Computer and System Sciences. 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9.
7. ^ a b c Beat, Gfeller; Sanders, Peter (2009). "Towards Optimal Range Medians". ICALP (1): 475–486.
8. ^ a b Bose, P; Kranakis, E.; Morin, P.; Tang, Y. (2005). "Approximate range mode and range median queries". In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS 2005), volume 3404 of Lecture Notes in ComputerScience: 377–388.