Range query (data structures)

Range minimum query reduced to the lowest common ancestor problem.

When the function of interest in a range query is a semigroup operator, the notion of ${\displaystyle f^{-1}}$ is not always defined, so the strategy in the previous section does not work. Andrew Yao showed[3] that there exists an efficient solution for range queries that involve semigroup operators. He proved that for any constant c, a preprocessing of time and space ${\displaystyle \theta (c\cdot n)}$ allows to answer range queries on lists where 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 _{i,j}(A)}$ 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)}$. One such solution is based on the equivalence between this problem and the lowest common ancestor problem.

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 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. A range minimum query ${\displaystyle \min _{i,j}(A)}$ is the lowest common ancestor in ${\displaystyle T_{A}}$ of ${\displaystyle a_{i}}$ and ${\displaystyle a_{j}}$. Because the lowest common ancestor can be solved in constant time using a preprocessing of time and space ${\displaystyle O(n)}$, range minimum query can as well. The solution when ${\displaystyle f=\max }$ is analogous. Cartesian trees can be constructed in linear time.

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 {\frac {1}{2}}}$
${\displaystyle O\left({\frac {n^{2}\log \log n}{\log n}}\right)}$	${\displaystyle O(1)}$

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

This particular case is of special interest since finding the median has several applications.[5] 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.[6] However its generalization through range median queries is recent.[7] A range median query ${\displaystyle \operatorname {median} (A,i,j)}$ where A,i and j have the usual meanings returns the median element of ${\displaystyle A[i,j]}$. Equivalently, ${\displaystyle \operatorname {median} (A,i,j)}$ should return the element of ${\displaystyle A[i,j]}$ of rank ${\displaystyle {\frac {j-i}{2}}}$. Range median queries cannot 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 a version where all the preprocessing is done up front. The offline version can be solved with ${\displaystyle O(n\log k+k\log n)}$ time and ${\displaystyle O(n\log k)}$ space.

The following pseudocode of the quickselect algorithm shows how to find the element of rank 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}}}$.[7]

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 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; otherwise we should look for the element of rank ${\displaystyle (r-t)}$ in A.high. To find 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 t fractional cascading should be used). If a linear algorithm to find the medians is used, the total cost of preprocessing for k range median queries is ${\displaystyle n\log k}$. The algorithm can also be modified to solve the online version of the problem.[7]