基于ST表的RMQ

RMQ算法，是一个快速求区间最值的离线算法，预处理时间复杂度O(n*log(n))查询O(1)，所以是一个很快速的算法，当然这个问题用线段树同样能够解决。

问题：给出n个数ai，让你快速查询某个区间的的最值。

算法分析：

（1）预处理

这个算法就是基于DP和位运算符，我们用 dp[i][j] 表示从第 i 位开始，到第 i + 2^j -1 位的最大值或者最小值。

那么我求dp[i][j的时候可以把它分成两部分，第一部分从 i 到 i + 2 ^( j-1 ) - 1 ，第二部分从 i + 2 ^( j-1 ) 到 i + 2^j - 1 次方，其实我们知道二进制数后一个是前一个的二倍，那么可以把 i ~i + 2^j 这个区间通过2^(j-1) 分成相等的两部分，那么转移方程很容易就写出来了。

转移方程：dp [ i ] [ j ] = max ( dp [ i ] [ j - 1 ] , dp [ i + ( 1 << ( j - 1 ) ) ] [ j - 1 ] )

以求区间最小值为例

void RMQ()

{

    for(int i=1;i<=N;i++)

        dp[i][0]=a[i]; //初始化, dp[i][0]就表示第i个数字本身

    for(int j = 1; (1<<j) <= N; j++)

        for(int i = 1; i+(1<<j)-1 <= N; i++)

            dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1]);

}

需要注意的是循环的顺序，我们发现外层是j，内层为i

（2）查询

假如我们需要查询的区间为(i,j)，那么我们需要找到覆盖这个闭区间(左边界取i，右边界取j)的最小幂（可以重复，比如查询5，6，7，8，9，我们可以查询5678和6789）

因为这个区间的长度为j - i + 1,所以我们可以取k=log2( j - i + 1)，则有：RMQ(A, i, j)=max{ F[i , k], F[ j - 2 ^ k + 1, k] }（可用数学证明，在此不加以论述）

eg. 要求区间[2，8]的最大值，k = log2（8 - 2 + 1）= 2，即求max(F[2, 2]，F[8 - 2 ^ 2 + 1, 2]) = max(F[2, 2]，F[5, 2])；

需要注意一个地方，就是<<运算符和+-运算符的优先级

比如这个表达式：5 - 1 << 2是多少？

答案是：4 * 2 * 2 = 16。所以我们要写成5 - (1 << 2)才是5-1 * 2 * 2 = 1

巴特西

基于ST表的RMQ

最新文章

热门文章