ST表
作者:
routine_89
,
2024-02-01 14:51:10
,
所有人可见
,
阅读 69
//st表
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+50;
int st[N][64]; //st[i][j]表示以i为左端点长度为2^j区间的最值[i,2^j-1];
int a[N],n;
void ST_prework()
{
for(int i=1;i<=n;i++) st[i][0]=a[i];
for(int j=1;(1<<j)<=n;j++) //2^j<=n
for(int i=1;i+(1<<j)-1<=n;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int ST_query(int l,int r)
{
if(l>r) return -1;
int k=log(r-l+1)/log(2); //2^k<r-l+1<=2^(k+1)
return max(st[l][k],st[r-(1<<k)+1][k]); //以l开始的2^k个数,和已r结尾向前2^k个数
//一定覆盖整个区间
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
ST_prework();
cout<<ST_query(1,n);
}