{% blockquote 百度百科 <a href="http://baike.baidu.com/view/1536346.htm">http://baike.baidu.com/view/1536346.htm</a> RMQ 问题 %} 
RMQ ( Range Minimum / Maximum Query )问题是指：
<blockquote>
对于长度为 <code>n</code> 的数列 A ，回答若干询问 <code>RMQ(A,i,j)</code> ( <code>i,j&lt;=n</code> )，返回数列 A 中下标在 <code>i</code> , <code>j</code> 里的最小(大)值 
也就是说，RMQ 问题是指求区间最值的问题 
{% endblockquote %}
</blockquote>

显然,最直观的算法是用 O(n) 的时间找到查询范围内的最值,然后输出 
当查询的次数 <code>m</code> 非常大时,时间复杂度是 <code>O(n*m)</code> 
很可能是一个非常大的数字
于是有了一些其他的查询方法:
<ol>
<li>
预处理区间 
用 <code>O(n2)</code> 的时间进行预处理 
分别用 <code>Max[i][j]</code> 、 <code>Min[i][j]</code> 表示 <code>[i,j]</code> 的最值 
预处理时间 <code>O(n2)</code> 
单次查询时间 <code>O(1)</code> 
总时间 <code>O(n2) + m * O(1)</code> 
显然,当 <code>n</code> 比较大时,这种方法并不好
</li>
<li>
<a href="/post/Algorithm/Segment_tree.html">&gt;线段树&lt;</a> 
通过二分法,用 <code>O(logn)</code> 的时间建树,再用 <code>O(logn)</code> 的时间查询 
总时间 <code>O(logn) + m * O(logn)</code> 
综合来看时间复杂度能够接受,但是由于需要构建二叉树,因此对内存的占用较大
</li>
<li>
<a href="/post/Algorithm/ST.html">&gt;ST算法&lt;</a> 
将线段分成一个个 <code>[i,i+2k-1]</code> 的区间 
采用动态规划的方法在 <code>O(nlogn)</code> 的时间内预处理 
采用数学方法,在 <code>O(1)</code> 的时间内完成一次查询 
总时间 <code>O(nlogn) + m * O(1)</code> 
综合时间复杂度较低,并且对内存占用也比较小 
是解决RMQ问题的最好方法
</li>
</ol>