范围最值查询 范围最值查询英語Range Minimum Query是针对数据集的一种条件查询若给定一个数组 A    n  displaystyle An 范围最值查询指定一个范围条件 i displaystyle i 到 j displaystyle j 要求取出 A  i  j  displaystyle Aij 中最大小的元素 若 A                     displaystyle A 条件为      displaystyle  的范围最值查询返回它是子数组 A                    displaystyle A 中最小的元素 通常情况下数组A是静态的即元素不会变化例如插入删除和修改等而所有的查询是以在线的方式给出的即预先并不知道所有查询的参数 RMQ问题有预处理 O  n  displaystyle On 之后每次查询 O    displaystyle O 的算法 范围最值查询问题RMQ与最近公共祖先LCA问题有直接联系它们可以互相转化RMQ的算法常常应用在严格或者近似子串匹配等问题的处理中