ST算法

发表于

ST算法用于区间最值问题，在O(N log N)的预处理后能以O(1)在线回答数列A中下标l~r之间的数的最大值

该算法利用了倍增的思想

初始化

设F[i,j]表示从i开始的2^j个数的最大值 即子区间[i,i+2^j-1]的最大值

递推边界 F[i,0]=A[i]

在递推时，我们把子区间成倍增长，有

F[i,j]=max(F[i,j-1],F[i+2^j,j-1])

即长度为2^j的子区间左右两端长度为2^(j-1)的子区间中值较大的那一个

询问

在询问任意区间[l,r]时，先计算一个k,满足2^k<r-l+1<=2^(k+1)

也就是使2的k次幂小于区间长度的前提下最大的k

那么从l开始的2^k个数 和 以r结尾的2^k个数这两段一定覆盖了整个区间[l,r]

这两段的最大值分别为F[l,k]和F[r-2^k+1,k]二者较大即所求

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int n,m;
int a[100001];
int f[100001][20];
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void pre(){//初始化
	for(int i=1;i<=n;++i)
	f[i][0]=a[i];
	int t=log(n)/log(2)+1;
	for(int j=1;j<t;++j){
		for(int i=1;i<=n-(1<<j)+1;++i)
		f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
}
int ask(int l,int r){
	 int k=log(r-l+1)/log(2);
	 return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;++i)a[i]=read();
	pre();
	for(int i=1;i<=m;++i){
		int x,y;
		x=read();y=read();
		printf("%d\n",ask(x,y));
	}
}