问题引入

先让我们看一个简单的问题，有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;

}

st表

「学习笔记」ST表

问题引入

过程

代码

推荐题目