Sliding range minimum query - Revision history

162.158.63.56: Undo revision 2221 by 162.158.62.53 (talk)

2021-04-04T21:33:54Z

Undo revision 2221 by 162.158.62.53 (talk)

162.158.62.53: Blanked the page

2021-03-05T20:17:01Z

Blanked the page

62.141.0.146: added problem from CodeChef (Betlista)

2012-09-17T07:15:25Z

added problem from CodeChef (Betlista)

Brian at 06:04, 10 June 2011

2011-06-10T06:04:15Z

Brian at 23:46, 5 June 2011

2011-06-05T23:46:09Z

Brian at 23:42, 5 June 2011

2011-06-05T23:42:10Z

Brian: Created page with "The '''sliding range minimum query''' is a special case of the static range minimum query that occurs when the query intervals are successive positions of a [[sliding window]..."

2011-06-01T06:07:38Z

Created page with "The '''sliding range minimum query''' is a special case of the static range minimum query that occurs when the query intervals are successive positions of a [[sliding window]..."

New page

The '''sliding range minimum query''' is a special case of the static [[range minimum query]] that occurs when the query intervals are successive positions of a [[sliding window]]. That is, suppose that the query intervals are <math>[a_1, b_1], [a_2, b_2], ..., [a_n, b_n]</math> such that the <math>a</math>'s are increasing and the <math>b</math>'s are also increasing (in both cases, not necessarily strictly). This would be an instance of sliding range minimum query. This special case is important because it can be solved in linear time (that is, linear in the size of the array plus the number of query intervals) and requires no preprocessing. In particular, the algorithm will first find the range minimum for the leftmost query interval, then the second leftmost, and so on, and does not need to examine an element of the array until just before computing the minimum in the first query interval that actually contains this element; this means the results of earlier queries may be used to compute elements of the array and additional query intervals further to the right "on the fly".

← Older revision	Revision as of 21:33, 4 April 2021
Line 1:	Line 1:
	+	The '''sliding range minimum query''' is a special case of the static [[range minimum query]] that occurs when the query intervals are successive positions of a [[sliding window]]. That is, suppose that the query intervals are <math>[a_1, b_1], [a_2, b_2], ..., [a_n, b_n]</math> such that the <math>a</math>'s are increasing and the <math>b</math>'s are also increasing (in both cases, not necessarily strictly). This would be an instance of sliding range minimum query. This special case is important because it can be solved in linear time (that is, linear in the size of the array plus the number of query intervals) and requires no preprocessing. In particular, the algorithm will first find the range minimum for the leftmost query interval, then the second leftmost, and so on, and does not need to examine an element of the array until just before computing the minimum in the first query interval that actually contains this element; this means the results of earlier queries may be used to compute elements of the array and additional query intervals further to the right "on the fly".

	+	===First attempt===
	+	We start by assuming there is a [[data structure]] that will allow us to do three things efficiently:
	+	# ''Insert'' a new element with a specified value.
	+	# ''Remove'' an element with a specified value.
	+	# ''Query'' the minimum value currently contained within.
	+	Then, we could proceed by straightforward simulation; as we proceed from one position of the sliding window to the next, adding and removing elements, we add to and remove from the data structure the same elements, so that upon attaining a new position we can query the minimum element in the data structure and it will match the minimum element in the current interval.
	+
	+	It turns out that an [[ordered dynamic set]] will do ''insert'' and ''remove'' in logarithmic time and ''query'' in constant time. This gives a time bound of <math>O(N \log N + Q)</math> where <math>N</math> is the size of the array and <math>Q</math> is the number of query intervals, since no element will be inserted more than once or removed more than once. This solution is not asymptotically optimal, and it also has a large constant factor for the [[balanced binary search tree]] that is probably used to implement the set.
	+
	+	===Refinement===
	+	To obtain a better solution, we begin by observing that the minimum can only decrease when a new element is added on the right and increase when an element is removed from the left:
	+	* If a new element is added on the right and it is smaller than the current minimum, then the minimum decreases.
	+	* When an element is removed from the left, the minimum will increase only if the removed element ''was'' the minimum.
	+	Consider further what happens to the ''previous'' value in the first case: if a new element is added on the right and it is smaller than the current minimum, then the current minimum element will ''never'' be the minimum again. This is because it could only regain its status if the new element were removed, but it will itself be removed before the new element will (since it is further to the left.)
	+
	+	This leads us to formulate a Lemma.
	+
	+	''Lemma'': Suppose all elements of the array are distinct. Then, each element in the array will be the minimum either over a range of consecutive query intervals (''i.e.'', for queries <math>i, i+1, i+2, ..., j</math> and only those queries) or never at all.
	+
	+	''Proof'': Suppose element <math>x</math> at index <math>k</math> first becomes the minimum for query interval <math>i</math>. Then, it will remain the minimum until either it is removed (in which case it will never be the minimum again) or until a smaller element is added (in which case, as explained above, again, it will never be the minimum again).
	+
	+	If the elements of the array are not distinct, a similar result still holds, assuming we have some way of breaking ties between elements with identical values (for example, the leftmost one is always considered the smallest).
	+
	+	The proof of the Lemma calls to mind two further observations:
	+	# Whenever an element is ousted from its position as the minimum, it is always replaced by one further to the right.
	+	# An element will never have a chance to be the minimum after a smaller element is added to its right.
	+
	+	Now, what if, whenever we add an element, we remove all the larger elements to its left? We can do this because those elements will never again be the minimum. If we do this, then our data structure will have the property that ''elements added later are always larger''. This means ''the minimum element will always be the one added first''. Furthermore, when this element is removed from the left as the sliding window moves, it is always the ''next oldest'' element that replaces it as the minimum.
	+
	+	We can now use a [[deque]] as our data structure, where most recently added elements are near the front and oldest elements near the back. When adding a new element on the right, first pop off all the larger elements from the front. When removing an old element from the left, simply pop it off the back. The element at the back will always be minimal. This gives the promised linear time bound without any precomputation.
	+
	+	===Problems===
	+	* {{Problem\|smac081p3\|Jumpscotch}}
	+	* {{Problem\|ioi0612\|IOI '06 - Pyramid}}
	+	* {{SPOJ\|MATRIX2\|Submatrix of Submatrix @ SPOJ}}
	+	* [http://www.codechef.com/problems/CHEFTOWN ChefTown Parade @ CodeChef]
	+
	+	[[Category:Pages needing code]]

← Older revision		Revision as of 20:17, 5 March 2021
Line 1:		Line 1:
−	The '''sliding range minimum query''' is a special case of the static [[range minimum query]] that occurs when the query intervals are successive positions of a [[sliding window]]. That is, suppose that the query intervals are <math>[a_1, b_1], [a_2, b_2], ..., [a_n, b_n]</math> such that the <math>a</math>'s are increasing and the <math>b</math>'s are also increasing (in both cases, not necessarily strictly). This would be an instance of sliding range minimum query. This special case is important because it can be solved in linear time (that is, linear in the size of the array plus the number of query intervals) and requires no preprocessing. In particular, the algorithm will first find the range minimum for the leftmost query interval, then the second leftmost, and so on, and does not need to examine an element of the array until just before computing the minimum in the first query interval that actually contains this element; this means the results of earlier queries may be used to compute elements of the array and additional query intervals further to the right "on the fly".

−	~~===First attempt===~~
−	~~We start by assuming there is a [[data structure]] that will allow us to do three things efficiently:~~
−	~~# ''Insert'' a new element with a specified value.~~
−	~~# ''Remove'' an element with a specified value.~~
−	~~# ''Query'' the minimum value currently contained within.~~
−	Then, we could proceed by straightforward simulation; as we proceed from one position of the sliding window to the next, adding and removing elements, we add to and remove from the data structure the same elements, so that upon attaining a new position we can query the minimum element in the data structure and it will match the minimum element in the current interval.
−
−	It turns out that an [[ordered dynamic set]] will do ''insert'' and ''remove'' in logarithmic time and ''query'' in constant time. This gives a time bound of <math>O(N \log N + Q)</math> where <math>N</math> is the size of the array and <math>Q</math> is the number of query intervals, since no element will be inserted more than once or removed more than once. This solution is not asymptotically optimal, and it also has a large constant factor for the [[balanced binary search tree]] that is probably used to implement the set.
−
−	~~===Refinement===~~
−	~~To obtain a better solution, we begin by observing that the minimum can only decrease when a new element is added on the right and increase when an element is removed from the left:~~
−	* If a new element is added on the right and it is smaller than the current minimum, then the minimum decreases.
−	* When an element is removed from the left, the minimum will increase only if the removed element ''was'' the minimum.
−	Consider further what happens to the ''previous'' value in the first case: if a new element is added on the right and it is smaller than the current minimum, then the current minimum element will ''never'' be the minimum again. This is because it could only regain its status if the new element were removed, but it will itself be removed before the new element will (since it is further to the left.)
−
−	~~This leads us to formulate a Lemma.~~
−
−	''Lemma'': Suppose all elements of the array are distinct. Then, each element in the array will be the minimum either over a range of consecutive query intervals (''i.e.'', for queries <math>i, i+1, i+2, ..., j</math> and only those queries) or never at all.
−
−	''Proof'': Suppose element <math>x</math> at index <math>k</math> first becomes the minimum for query interval <math>i</math>. Then, it will remain the minimum until either it is removed (in which case it will never be the minimum again) or until a smaller element is added (in which case, as explained above, again, it will never be the minimum again).
−
−	If the elements of the array are not distinct, a similar result still holds, assuming we have some way of breaking ties between elements with identical values (for example, the leftmost one is always considered the smallest).
−
−	~~The proof of the Lemma calls to mind two further observations:~~
−	~~# Whenever an element is ousted from its position as the minimum, it is always replaced by one further to the right.~~
−	~~# An element will never have a chance to be the minimum after a smaller element is added to its right.~~
−
−	Now, what if, whenever we add an element, we remove all the larger elements to its left? We can do this because those elements will never again be the minimum. If we do this, then our data structure will have the property that ''elements added later are always larger''. This means ''the minimum element will always be the one added first''. Furthermore, when this element is removed from the left as the sliding window moves, it is always the ''next oldest'' element that replaces it as the minimum.
−
−	We can now use a [[deque]] as our data structure, where most recently added elements are near the front and oldest elements near the back. When adding a new element on the right, first pop off all the larger elements from the front. When removing an old element from the left, simply pop it off the back. The element at the back will always be minimal. This gives the promised linear time bound without any precomputation.
−
−	~~===Problems===~~
−	* {{Problem\|smac081p3\|Jumpscotch}}
−	* {{Problem\|ioi0612\|IOI '06 - Pyramid}}
−	* {{SPOJ\|MATRIX2\|Submatrix of Submatrix @ SPOJ}}
−	* [http://www.codechef.com/problems/CHEFTOWN ChefTown Parade @ CodeChef]
−
−	~~[[Category:Pages needing code]]~~

@@ Line 36: / Line 36: @@
 * {{Problem|ioi0612|IOI '06 - Pyramid}}
 * {{SPOJ|MATRIX2|Submatrix of Submatrix @ SPOJ}}
 [[Category:Pages needing code]]

← Older revision		Revision as of 06:04, 10 June 2011
Line 36:		Line 36:
	* {{Problem\|ioi0612\|IOI '06 - Pyramid}}		* {{Problem\|ioi0612\|IOI '06 - Pyramid}}
	* {{SPOJ\|MATRIX2\|Submatrix of Submatrix @ SPOJ}}		* {{SPOJ\|MATRIX2\|Submatrix of Submatrix @ SPOJ}}
		+
		+	[[Category:Pages needing code]]

← Older revision		Revision as of 23:46, 5 June 2011
Line 31:		Line 31:

	We can now use a [[deque]] as our data structure, where most recently added elements are near the front and oldest elements near the back. When adding a new element on the right, first pop off all the larger elements from the front. When removing an old element from the left, simply pop it off the back. The element at the back will always be minimal. This gives the promised linear time bound without any precomputation.		We can now use a [[deque]] as our data structure, where most recently added elements are near the front and oldest elements near the back. When adding a new element on the right, first pop off all the larger elements from the front. When removing an old element from the left, simply pop it off the back. The element at the back will always be minimal. This gives the promised linear time bound without any precomputation.
		+
		+	===Problems===
		+	* {{Problem\|smac081p3\|Jumpscotch}}
		+	* {{Problem\|ioi0612\|IOI '06 - Pyramid}}
		+	* {{SPOJ\|MATRIX2\|Submatrix of Submatrix @ SPOJ}}

← Older revision		Revision as of 23:42, 5 June 2011
Line 1:		Line 1:
	The '''sliding range minimum query''' is a special case of the static [[range minimum query]] that occurs when the query intervals are successive positions of a [[sliding window]]. That is, suppose that the query intervals are <math>[a_1, b_1], [a_2, b_2], ..., [a_n, b_n]</math> such that the <math>a</math>'s are increasing and the <math>b</math>'s are also increasing (in both cases, not necessarily strictly). This would be an instance of sliding range minimum query. This special case is important because it can be solved in linear time (that is, linear in the size of the array plus the number of query intervals) and requires no preprocessing. In particular, the algorithm will first find the range minimum for the leftmost query interval, then the second leftmost, and so on, and does not need to examine an element of the array until just before computing the minimum in the first query interval that actually contains this element; this means the results of earlier queries may be used to compute elements of the array and additional query intervals further to the right "on the fly".		The '''sliding range minimum query''' is a special case of the static [[range minimum query]] that occurs when the query intervals are successive positions of a [[sliding window]]. That is, suppose that the query intervals are <math>[a_1, b_1], [a_2, b_2], ..., [a_n, b_n]</math> such that the <math>a</math>'s are increasing and the <math>b</math>'s are also increasing (in both cases, not necessarily strictly). This would be an instance of sliding range minimum query. This special case is important because it can be solved in linear time (that is, linear in the size of the array plus the number of query intervals) and requires no preprocessing. In particular, the algorithm will first find the range minimum for the leftmost query interval, then the second leftmost, and so on, and does not need to examine an element of the array until just before computing the minimum in the first query interval that actually contains this element; this means the results of earlier queries may be used to compute elements of the array and additional query intervals further to the right "on the fly".
		+
		+	===First attempt===
		+	We start by assuming there is a [[data structure]] that will allow us to do three things efficiently:
		+	# ''Insert'' a new element with a specified value.
		+	# ''Remove'' an element with a specified value.
		+	# ''Query'' the minimum value currently contained within.
		+	Then, we could proceed by straightforward simulation; as we proceed from one position of the sliding window to the next, adding and removing elements, we add to and remove from the data structure the same elements, so that upon attaining a new position we can query the minimum element in the data structure and it will match the minimum element in the current interval.
		+
		+	It turns out that an [[ordered dynamic set]] will do ''insert'' and ''remove'' in logarithmic time and ''query'' in constant time. This gives a time bound of <math>O(N \log N + Q)</math> where <math>N</math> is the size of the array and <math>Q</math> is the number of query intervals, since no element will be inserted more than once or removed more than once. This solution is not asymptotically optimal, and it also has a large constant factor for the [[balanced binary search tree]] that is probably used to implement the set.
		+
		+	===Refinement===
		+	To obtain a better solution, we begin by observing that the minimum can only decrease when a new element is added on the right and increase when an element is removed from the left:
		+	* If a new element is added on the right and it is smaller than the current minimum, then the minimum decreases.
		+	* When an element is removed from the left, the minimum will increase only if the removed element ''was'' the minimum.
		+	Consider further what happens to the ''previous'' value in the first case: if a new element is added on the right and it is smaller than the current minimum, then the current minimum element will ''never'' be the minimum again. This is because it could only regain its status if the new element were removed, but it will itself be removed before the new element will (since it is further to the left.)
		+
		+	This leads us to formulate a Lemma.
		+
		+	''Lemma'': Suppose all elements of the array are distinct. Then, each element in the array will be the minimum either over a range of consecutive query intervals (''i.e.'', for queries <math>i, i+1, i+2, ..., j</math> and only those queries) or never at all.
		+
		+	''Proof'': Suppose element <math>x</math> at index <math>k</math> first becomes the minimum for query interval <math>i</math>. Then, it will remain the minimum until either it is removed (in which case it will never be the minimum again) or until a smaller element is added (in which case, as explained above, again, it will never be the minimum again).
		+
		+	If the elements of the array are not distinct, a similar result still holds, assuming we have some way of breaking ties between elements with identical values (for example, the leftmost one is always considered the smallest).
		+
		+	The proof of the Lemma calls to mind two further observations:
		+	# Whenever an element is ousted from its position as the minimum, it is always replaced by one further to the right.
		+	# An element will never have a chance to be the minimum after a smaller element is added to its right.
		+
		+	Now, what if, whenever we add an element, we remove all the larger elements to its left? We can do this because those elements will never again be the minimum. If we do this, then our data structure will have the property that ''elements added later are always larger''. This means ''the minimum element will always be the one added first''. Furthermore, when this element is removed from the left as the sliding window moves, it is always the ''next oldest'' element that replaces it as the minimum.
		+
		+	We can now use a [[deque]] as our data structure, where most recently added elements are near the front and oldest elements near the back. When adding a new element on the right, first pop off all the larger elements from the front. When removing an old element from the left, simply pop it off the back. The element at the back will always be minimal. This gives the promised linear time bound without any precomputation.