RMQ算法

发表于

RMQ算法用途

RMQ算法：对于任意给定的一个数列a,求RMQ(a,i,j)就是求a数列中[i,j]中的最大值和最小值。

时间复杂度

RMQ算法是快速求区间最值得离线算法，预处理的复杂度为O(n*logn),查询O(1)[用线段树也可以做，RMQ算法主要用到了DP的思想]

算法实现

DP+位运算