RMQ(Range Mininum/Maxinum Query)
区间最值问题
解决方法
若需要修改，常常使用线段树等数据结构。
若不需要修改，一般使用st表。
例题
给定M及N个数（1<N<=2500000），每个数在0到100000之间。
输出每M个数中的最大数，即1M中的最大数，2M+1中的最大数……，N-M+1~N中的最大数，共N-M+1个。
数组
将读入的数据放到一个线性表f数组中，然后枚举开始点i，遍历求出区间[i,i+m-1]中最大值。
堆
将数据组织成树型结构，即将读入的数值设计成一个大根堆，则堆顶元素就是全局最大值，记录下每个数值在输入时的位置。
由于本题是求一个指定区间的最大值，还需要判断一下堆顶元素是否位于指定区间，如果在，则直接输出堆顶元素的值，否则踢掉堆顶元素。
单调队列
用f(i)代表第i个数对应的答案，a[i]表示第i个数。
于是维护这样一个队列：队列中的每个元素有两个域{position,value}，分别代表他在原队列中的位置和值，我们随时保持这个队列中的元素position域单调递增,value域单调递减,。
则在计算f(i)的时候，先将a[i]加入到队列中。
我们让a[i]与队尾元素的value域进行比较，但凡发现小于a[i]的，一律从队列中踢掉。
由于i-m+1是随着i单调递增的，所以对于任意j<i,有a[j]<a[i]，在计算任意一个状态f(x)(x<i)的时候，j都不会比i优，所以j被踢掉是有理有据的.
通过“踢数据”的操作，我们有效地降低了需要维护的数据量。
对比堆的操作中，这些无效的数据仍放在堆中，在加数据的操作时，无疑增加了操作的次数。
采用这种方法，每个数据进出队列都只有一次，所以时间复杂度为\(O(n)\),而堆的时间复杂度为\(O(nlog_{2}n)\)。
接下来我们需要在队首不断删除，直到队首的position大于等于i-m+1，此时队首的value必定是f(i)的结果，因为队列是单调的。
st表
线段树
并非原创，仅是整理，请见谅
Lo问我为什么看星星。我觉得银河和代码是同一种东西，这也是一种回答。————Co 【文章转自：香港多IP服务器 http://www.558idc.com/hkzq.html提供，感恩】