Range minimum query - Revision history

188.120.84.157: /* Dynamic */

2014-04-24T16:46:49Z

‎Dynamic

167.220.225.236: /* Sparse table */

2014-03-05T06:10:34Z

‎Sparse table

Dhruvbird: /* Dynamic */

2012-10-10T06:19:34Z

‎Dynamic

Brian: needs code

2011-11-28T08:38:26Z

needs code

Brian at 08:37, 28 November 2011

2011-11-28T08:37:16Z

Show changes

Brian: Created page with "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 [[tot..."

2011-11-21T05:35:22Z

Created page with "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 [[tot..."

New page

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>.



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

@@ Line 44: / Line 44: @@
 ==Dynamic==
-The block-based solution handles the dynamic case as well; we must simply remember, whenever we update an element, to recompute the minimum element in the block it is in. This gives <math>O(\sqrt{n})</math> time per update, and, assuming a uniform random distribution of updates, the expected update time is constant. This is because if we decrease an element, we need only check whether the new value is less than the current minimum (constant time), whereas if we increase an element, we only need to recompute the minimum if the element updated was the minimum before (which takes <math>O(\sqrt{n})</math> time but has a probability of occurring of only <math>O(1/m) = O(1/\sqrt{n})</math>). Unfortunately, the query still has average-case time <math>O(\sqrt{n})</math>.
+The block-based solution handles the dynamic case as well; we must simply remember, whenever we update an element, to recompute the minimum element in the block it is in. This gives <math>O(\sqrt{n})</math> time per update, and, assuming a uniform random distribution of updates, the expected update time is <math>O(1)</math>. This is because if we decrease an element, we need only check whether the new value is less than the current minimum (constant time), whereas if we increase an element, we only need to recompute the minimum if the element updated was the minimum before (which takes <math>O(\sqrt{n})</math> time but has a probability of occurring of only <math>O(1/m) = O(1/\sqrt{n})</math>). Unfortunately, the query still has average-case time <math>O(\sqrt{n})</math>.
 The [[segment tree]] can be computed in linear time and allows both queries and updates to be answered in <math>O(\log n)</math> time. It also allows, with some cleverness, entire ranges to be updated at once (efficiently). Analysis of the average case is left as an exercise to the reader.

@@ Line 26: / Line 26: @@
 ===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>\lfloor\log(b-a)\rfloor</math>; and then the answer is <math>\min(M_{a,k}, M_{b-2^k,k})</math>.
+(Namely 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>\lfloor\log(b-a)\rfloor</math>; and then the answer is <math>\min(M_{a,k}, M_{b-2^k,k})</math>.
 ===Cartesian trees===

← Older revision		Revision as of 06:19, 10 October 2012
Line 47:		Line 47:

	The [[segment tree]] can be computed in linear time and allows both queries and updates to be answered in <math>O(\log n)</math> time. It also allows, with some cleverness, entire ranges to be updated at once (efficiently). Analysis of the average case is left as an exercise to the reader.		The [[segment tree]] can be computed in linear time and allows both queries and updates to be answered in <math>O(\log n)</math> time. It also allows, with some cleverness, entire ranges to be updated at once (efficiently). Analysis of the average case is left as an exercise to the reader.
		+
		+	We can also use any balanced binary tree (or dictionary data structure such as a skip-list) and augment it to support range minimum query operations with O(log n) per Update (Insert/Delete) as well as Query.

	==References==		==References==

← Older revision		Revision as of 08:38, 28 November 2011
Line 51:		Line 51:
	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/>
		+
		+	[[Category:Pages needing code]]