如何高效使用RMQ进行实时数据查询？

本文共计761个文字，预计阅读时间需要4分钟。

RMQ（范围最小/最大查询）+ 区间最值问题 + 解决方法 + 若需要修改，通常使用线段树等数据结构。一般使用st表。+ 例题 + 给定M个N个数（1N=2500000），每个数在0到1000000之间。+ 输入

RMQ(Range Mininum/Maxinum Query)

区间最值问题

解决方法

若需要修改，常常使用线段树等数据结构。

若不需要修改，一般使用st表。

例题

给定M及N个数（1<N<=2500000），每个数在0到100000之间。

输出每M个数中的最大数，即1_{M中的最大数，2}M+1中的最大数……，N-M+1~N中的最大数，共N-M+1个。

数组

将读入的数据放到一个线性表f数组中，然后枚举开始点i，遍历求出区间[i,i+m-1]中最大值。

堆

将数据组织成树型结构，即将读入的数值设计成一个大根堆，则堆顶元素就是全局最大值，记录下每个数值在输入时的位置。

由于本题是求一个指定区间的最大值，还需要判断一下堆顶元素是否位于指定区间，如果在，则直接输出堆顶元素的值，否则踢掉堆顶元素。

单调队列

用f(i)代表第i个数对应的答案，a[i]表示第i个数。

于是维护这样一个队列：队列中的每个元素有两个域{position,value}，分别代表他在原队列中的位置和值，我们随时保持这个队列中的元素position域单调递增,value域单调递减,。