ST表
ST表的功能很简单
它是解决RMQ问题(区间最值问题)的一种强有力的工具
它可以做到O(nlogn)预处理,O(1)查询最值
是一种处理静态区间可重复计算问题的数据结构,一般也就求求最大最小值辣。
ST表的思想是先求出每个[i, i + 2^k)的最值。
注意到这样区间的总数是O(N log N)的.
预处理
不妨令f为[i, i + 2^j)的最小值。
那么首先fi,0的值都是它本身。
而f = min(f, f)
这样在O(N log N)的时间内就处理好了整个ST表
询问
比如我们要询问[l, r]这个区间的最小值.
找到最大的k满足2^k ≤ r − l + 1.
取[l, l + 2^k), [r − 2^k + 1, r + 1)这两个区间。
注意到这两个区间完全覆盖了[l, r],所以这两个区间最小值
较小的一个就是[l, r]的最小值。
注意到每次询问只要找区间就行了,所以复杂度是O(1).
解释一下数组含义:
ST[j][i]为从j开始的长度为2^i的区间的最大值
Log[x]为比x小的最大的2^y 的y值(或者说是log x 下去整)
代码:
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<time.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps=1e-;
ll pp=;
ll mo(ll a,ll pp){if(a>= && a<pp)return a;a%=pp;if(a<)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=;for(;b;b>>=,a=mo(a*a,pp))if(b&)ans=mo(ans*a,pp);return ans;}
ll read(){
ll ans=;
char last=' ',ch=getchar();
while(ch<'' || ch>'')last=ch,ch=getchar();
while(ch>='' && ch<='')ans=ans*+ch-'',ch=getchar();
if(last=='-')ans=-ans;
return ans;
}
//head int m,n,a[],st[][],Log[]; int find(int a,int b)
{
int t=Log[b-a+];
return max(st[a][t],st[b-(<<t)+][t]);
//注意到对于[l,r],[l,l+2^x-1],[r-2^x+1,r]并起来是[l,r]
} int main()
{
n=read(),m=read();
rep(i,,n) a[i]=read();
rep(i,,n) st[i][]=a[i];
rep(i,,)
{
for(int j=;j+(<<i)-<=n;j++)
{
st[j][i]=max(st[j][i-],st[j+(<<(i-))][i-]);
//ST[j][i]为从j开始的长度为2^i的区间的最大值
//显然[j,j+2^i)=[j,j+2^(i-1))+[j+2^(i-1),j+2^i)=max(ST[i-1][j],ST[i-1][j+2^(i-1)])
}
}
for(int i=;(<<i)<;i++) Log[<<i]=i;
for(int i=;i<;i++)
{
if(Log[i]==) Log[i]=Log[i-];
//令Log[x]为比x小的最大的2^y
}
for(int i=;i<=m;i++)
{
int x,y;
x=read(),y=read();
printf("%d\n",find(x,y));
}
return ;
}