问题引入

先让我们看一个简单的问题,有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<cstdio>
#include<iostream>
#include<cctype>
#include<queue>
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;
}

推荐题目

  1. 洛谷 P3865【模板】ST表(等于Loj #10119. 「一本通 4.2 例 1」数列区间最大值 )
  2. 洛谷 P2251 质量检测
  3. Loj #10120. 「一本通 4.2 例 2」最敏捷的机器人
  4. Loj #10121. 「一本通 4.2 例 3」与众不同
  5. Loj #10122. 「一本通 4.2 练习 1」天才的记忆
  6. Bzoj [1699: Usaco2007 Jan]Balanced Lineup排队 (等于Loj #10123. 「一本通 4.2 练习 2」Balanced Lineup 洛谷 P2880 [USACO07JAN]平衡的阵容Balanced Lineup )
  7. NOIP 2011 提高组 选择客栈 :洛谷 P1311 选择客栈 Loj #2597. 「NOIP2011」选择客栈
05-11 20:07