Difference between revisions of "Sliding range minimum query"
(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]...") |
(No difference)
|
Revision as of 06:07, 1 June 2011
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 ![[a_1, b_1], [a_2, b_2], ..., [a_n, b_n]](/wiki/images/math/4/6/c/46c7762cfc306a393337755ab2ae1f62.png)
such that the 
's are increasing and the 
'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".
