Editing Range minimum query
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 1: | Line 1: | ||
− | The term '''range minimum query (RMQ)''' comprises all variations of the problem of finding the smallest element | + | 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 | + | 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== | ==Static== | ||
Line 8: | Line 8: | ||
===Sliding=== | ===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. | 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=== | ===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. | 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 | + | 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 | + | 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=== | ===Segment tree=== | ||
Line 26: | Line 20: | ||
===Sparse table=== | ===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=== | ===Cartesian trees=== | ||
We can get the best of both worlds—that is, constant query time and linear preprocessing time and space—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 can get the best of both worlds—that is, constant query time and linear preprocessing time and space—but the algorithm is somewhat more involved. It combines the block-based approach, the sparse table approach, and the use of [[Cartesian tree]]s. | ||
Line 35: | Line 30: | ||
''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> | ''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== | ==References== | ||
Much of the information in this article was drawn from a single source: | Much of the information in this article was drawn from a single source: | ||
<references/> | <references/> | ||
− | |||
− |