RMQ问题:对于长度为N的序列,询问区间[L,R]中的最值 RMQ问题的几种解法: 普通遍历查询,O(1)-O(N) 线段树,O(N)-O(logN) DP,O(NlogN)-O(1) RMQ标准算法,O(N)-O(1) 简单介绍: 朴素的查询,不需要任何预处理,但结果是没有任何已知的信息可以利用,每次都需要从头遍历到尾. 线段树,区间问题的神器,用线段树做比起朴素的暴力查询要快得多,关键在于线段树使用了分治思想,利用了区间问题的可合并性.任何一个区间最多只需要logN个线段树上的区间来合并,线