嗯...
题目链接：https://www.luogu.com.cn/problem/P3865
ST(Sparse Table)算法，运用了倍增的思想。
我们令f[i][k]数组表示区间[i, i + 2^k - 1]中的最小值。
显然有递推式：
f[i][0]=a[i]; f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1];
查询时：
区间[l, r]，求出k=log2(r-l+1)。于是可以用f[l][k]和f[r–2^j+1][j]来覆盖这个区间，得到最大值也即answer=max(f[l][k], f[r–(1 << j)+1][k])
AC代码：
1 #include<cstdio> 2 #include<cmath> 3 #include<iostream> 4 5 using namespace std; 6 int n,m; 7 int a[100005],st[100500][25]; 8 9 int main(){ 10 scanf("%d%d",&n,&m); 11 for(int i=1;i<=n;i++) { scanf("%d",&a[i]); st[i][0]=a[i];} 12 for(int j=1;j<=log2(n);j++){ 13 for(int i=1;i+(1<<j)-1<=n;i++){ 14 st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); 15 } 16 } 17 for(int i=1;i<=m;i++){ 18 int l,r; 19 scanf("%d%d",&l,&r); 20 int k=log2(r-l+1); 21 printf("%d\n",max(st[l][k],st[r-(1<<k)+1][k])); 22 } 23 return 0; 24 }
原文：https://www.cnblogs.com/New-ljx/p/12210090.html
