标签:: RMQ

0

「RMQ」区间最值问题详解

区间最值问题是用来解决问一个固定区间内多次询问某个子区间最值的快速算法。 那么我们先来说一下RMQ问题的比较快的算法—— ST(Sparse Table)算法是一个非常有名的在线处理RMQ问题的算法,它可以在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。 首先是预处理,用动态规划(DP)解决。设A[i]是要求区间最值的数列,F[i, j]表示从第i个数起连续2^j个数中的最大