Editing Range minimum query

The term '''range minimum query (RMQ)''' comprises all variations of the problem of finding the smallest element in a contiguous subsequence of a list of items taken from a [[totally ordered set]] (usually numbers). This is one of the most extensively-studied problems in computer science, and many algorithms are known, each of which is appropriate for a specific variation.

A single range minimum query is a set of indices <math>i < j</math> into an array <math>A</math>; the answer to this query is some <math>k \in [i,j]</math> such that <math>A_k \leq A_m</math> for all <math>m \in [i,j]</math>. In isolation, this query is answered simply by scanning through the range given and selecting the minimum element, which can take up to linear time. The problem is interesting because we often desire to answer a large number of queries, so that if, for example, 500000 queries are to be performed on a single array of 10000000 elements, then using this naive approach on each query individually is probably too slow.

==Static==
In the ''static range minimum query'', the input is an array and a set of intervals (contiguous subsequences) of the array, identified by their endpoints, and for each interval we must find the smallest element contained therein. Modifications to the array are not allowed, but we must be prepared to handle queries "on the fly"; that is, we might not know all of them at once.

===Sliding===
This problem can be solved in linear time in the special case in which the intervals are guaranteed to be given in such an order that they are successive elements of a [[sliding window]]; that is, each interval given in input neither starts earlier nor ends later than the previous one. This is the [[sliding range minimum query]] problem; an algorithm is given in that article.

===Division into blocks===
In all other cases, we must consider other solutions. A simple solution for this and other related problems involves splitting the array into equally sized blocks (say, <math>m</math> elements each) and precomputing the minimum in each block. This precomputation will take <math>\Theta(n)</math> time, since it takes <math>\Theta(m)</math> time to find the minimum in each block, and there are <math>\Theta(n/m)</math> blocks.

After this, when we are given some query <math>[a,b]</math>, we note that this can be written as the union of the intervals <math>[a,c_0), [c_0, c_1), [c_1, c_2), ..., [c_{k-1}, c_k), [c_k, b]</math>, where all the intervals except for the first and last are individual blocks. If we can find the minimum in each of these subintervals, the smallest of those values will be the minimum in <math>[a,b]</math>. But because all the intervals in the middle (note that there may be zero of these if <math>a</math> and <math>b</math> are in the same block) are blocks, their minima can simply be looked up in constant time.

Observe that the intermediate intervals are <math>O(n/m)</math> in number (because there are only about <math>n/m</math> blocks in total). Furthermore, if we pick <math>c_0</math> at the nearest available block boundary, and likewise with <math>c_k</math>, then the intervals <math>[a,c_0)</math> and <math>[c_k,b]</math> have size <math>O(m)</math> (since they do not cross block boundaries). By taking the minimum of all the precomputed block minima, and the elements in <math>[a,c_0)</math> and <math>[c_k,b]</math>, the answer is obtained in <math>O(m + n/m)</math> time. If we choose a block size of <math>m \approx \sqrt{n}</math>, we obtain <math>O(\sqrt{n})</math> overall.

===Segment tree===
While <math>O(\sqrt{n})</math> is not optimal, it is certainly better than linear time, and suggests that we might be able to do better using precomputation. Instead of dividing the array into <math>\sqrt{n}</math> pieces, we might consider dividing it in half, and then dividing each half in half, and dividing each quarter in half, and so on. The resulting structure of intervals and subintervals is a [[segment tree]]. It uses linear space and requires linear time to construct; and once it has been built, any query can be answered in <math>O(\log N)</math> time.

===Sparse table===
(Name due to <ref>"Range Minimum Query and Lowest Common Ancestor". (n.d.). Retrieved from http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Range_Minimum_Query_%28RMQ%29</ref>.) At the expense of space and preprocessing time, we can even answer queries in <math>O(1)</math> using [[dynamic programming]]. Define <math>M_{i,k}</math> to be the minimum of the elements <math>A_i, A_{i+1}, ..., A_{i+2^k-1}</math> (or as many of those elements as actually exist); that is, the elements in an interval of size <math>2^k</math> starting from <math>i</math>. Then, we see that <math>M_{i,0} = A_i</math> for each <math>i</math>, and <math>M_{i,k+1} = \min(M_{i,k}, M_{i+2^k,k})</math>; that is, the minimum in an interval of size <math>2^{k+1}</math> is the smaller of the minima of the two halves of which it is composed, of size <math>2^k</math>. Thus, each entry of <math>M</math> can be computed in constant time, and in total <math>M</math> has about <math>n\cdot \log n</math> entries (since values of <math>k</math> for which <math>2^k > n</math> are not useful). Then, given the query <math>[a,b]</math>, simply find <math>k</math> such that <math>[a,a+2^k)</math> and <math>(b-2^k,b]</math> overlap but are contained within <math>[a,b]</math>; then we already know the minima in each of these two sub-intervals, and since they cover the query interval, the smaller of the two is the overall minimum. It's not too hard to see that the desired <math>k</math> is <math>\lceil\log(b-a+1)\rceil</math>; and then the answer is <math>\min(M_{a,k}, M_{b-2^k+1,k})</math>.

<!-- The TopCoder tutorial doesn't quite make sense here. How is the difference array used?
===Cartesian trees===
We can get the best of both worlds&mdash;that is, constant query time and linear preprocessing time and space&mdash;but the algorithm is somewhat more involved. It combines the block-based approach, the sparse table approach, and the use of [[Cartesian tree]]s.

We observe that some minimum in a range in the given array occurs at the same place as the [[lowest common ancestor]] of the two nodes corresponding to the endpoints of the range in the Cartesian tree of the array. That is, if elements <math>A_i</math> and <math>A_j</math> occur at nodes <math>u</math> and <math>v</math> in the Cartesian tree of <math>A</math>, then there is some <math>A_k</math> in the range <math>A_{i..j}</math> such that the element <math>A_k</math> occurs at the lowest common ancestor of <math>u</math> and <math>v</math> in the Cartesian tree.

''Proof'': An inorder traversal of the Cartesian tree gives the original array. Thus, consider the segment <math>S</math> of the inorder traversal beginning when <math>u</math> is visited and <math>v</math> is visited (<math>u</math> and <math>v</math> are as above); this must be equivalent to the segment of the array <math>A_{i..j}</math>. Now, if the LCA of <math>u</math> and <math>v</math> is <math>u</math>, then <math>v</math> is in its right subtree; but <math>S</math> must then contain only <math>u</math> and elements from <math>u</math>'s right subtree, since all nodes in <math>S</math>'s right subtree (including <math>v</math>) will be visited immediately after <math>u</math> itself; so that all nodes in <math>S</math> are descendants of <math>u</math>. Likewise, if <math>v</math> is the LCA, then <math>S</math> consists entirely of descendants of <math>v</math>. If the LCA is neither <math>u</math> nor <math>v</math>, then <math>u</math> must occur in its left subtree and <math>v</math> in its right subtree (because if they both occurred in the same subtree, then the root of that subtree would be a lower common ancestor, a contradiction). But all elements in the left subtree of the LCA, including <math>u</math> are visited immediately before the LCA, and all elements in the right, including <math>v</math>, are visited immediately after the LCA, and hence, again, all nodes in <math>S</math> are descendants of the LCA. Now, the labels on the nodes in <math>S</math> correspond to the elements <math>A_i, ..., A_j</math>, and all nodes in <math>S</math> have labels less than or equal to the label of the LCA, since Cartesian trees are min-heap-ordered; so it follows that the label of the LCA is the minimum element in the range. <math>_{\blacksquare}</math>

LCA queries may be answered in <math>O(1)</math> time with <math>O(n)</math> preprocessing. This involves reducing LCA back to RMQ using the technique described in the [[Lowest common ancestor]] article, but now the difference between adjacent elements of the array, which we'll call <math>B</math>, is either +1 or -1. We construct array <math>C</math> such that <math>C_i = B_{i+1} - B_i</math>, so that <math>C_i = \pm 1</math> for all <math>i</math>. Then, given some query <math>[i,j]</math> on <math>B</math>, we observe that <math>B_k - B_i = C_i + C_{i+1} + ... + C_{k-1}</math>, and therefore the smallest element in the range is the one at index <math>k</math> for which <math>C_i + ... + C_{k-1}</math> is minimal.
-->

==References==
Much of the information in this article was drawn from a single source:
<references/>