问题引入

先让我们看一个简单的问题，有N个元素，Q次操作，每次操作需要求出一段区间内的最大/小值。

这就是著名的RMQ问题。

RMQ问题的解法有很多，如线段树、单调队列(某些情况下)、ST表等。这里主要探讨ST表

过程

ST表是一种神奇的算法,它以倍增与二进制为基础，实现区间内最大/小值。话不多说，直接切入正题——

我们这里以求区间最大值为例。

首先，我们可以用O(\(N lg N\))的时间复杂度预处理出以i开始，接下来2j个元素中的最大值。我们借助递推/DP的思想。

for ( int i = 1; i <= l; ++i )    for ( int j = 1; j + ( 1 << i ) - 1 <= n; ++j )        f[j][i] = max( f[j][i - 1], f[j + ( 1 << ( i - 1 ) )][i - 1] );

然后就可以以O(1)的复杂度求出任意两个区间的最大值辣。

假设要求[ x, y ] 区间内的最大值(因为区间相交对于最大值是没有影响的，所以可以直接把最接近区间长度的2的倍数设为2z，求出f[x][z]与f[y - ( 1 << z ) + 1][z]的最大值即可)。

printf( "%d\n", max( f[x][z], f[y - ( 1 << z ) + 1][z] ) );

为了保证复杂度为O(1) 我们采用一个数组预处理出1 ~ N 的log值

lg[1] = 0;for ( int i = 2; i <= N; ++i ) lg[i] = lg[i >> 1] + 1;

代码

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int N, Q;int f[100005][30];int lg[100005];int main(){    scanf( "%d%d", &N, &Q );    for ( int i = 1; i <= N; ++i ) scanf( "%d", &f[i][0] );//从i开始2^0(就是1)个元素的最大值就是它自己     lg[1] = 0;//2 ^ 0 = 1 所以lg 1 = 0     for ( int i = 2; i <= N; ++i ) lg[i] = lg[i >> 1] + 1;    int l(lg[N]);    for ( int i = 1; i <= l; ++i )//按长度从小到大，以保证较小长度已经完成         for ( int j = 1; j + ( 1 << i ) - 1 <= N; ++j )            f[j][i] = max( f[j][i - 1], f[j + ( 1 << ( i - 1 ) )][i - 1] );//如上所述     while( Q-- ){        int x, y, z;        scanf( "%d%d", &x, &y );        z = lg[y - x + 1];        printf( "%d\n", max( f[x][z], f[y - ( 1 << z ) + 1][z] ) );//如上所述     }    return 0;}

问题引入

过程

代码

推荐题目