可以使用线段树,实现 pushup、build、query 代码如下,单次使用线段树查询的时间复杂度是$O(logn)$,所以总共是$O(mlogn)$
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 200020;
int n,m;
int a[N];
struct Node{
int l,r,maxv;
}tr[4*N];
void pushup(int u){
tr[u].maxv=max(tr[u<<1].maxv,tr[u<<1|1].maxv);
}
void build(int u,int l,int r){
if(l==r) tr[u]={l,r,a[r]};
else{
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
int query(int u,int l,int r){
if(tr[u].l>=l && tr[u].r<=r) return tr[u].maxv;
int mid=tr[u].l+tr[u].r>>1;
int maxv=numeric_limits<int>::min();
if(l<=mid) maxv=max(query(u<<1,l,r),maxv);
if(r>mid) maxv=max(query(u<<1|1,l,r),maxv);
return maxv;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
build(1,1,n);
for(int i=0;i<m;i++){
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",query(1,a,b));
}
return 0;
}
也可以使用 Sparse Table 跳表(稀疏表),但 Sparse Table 只支持静态空间的查询操作。
ST 算法基于原理:一个大区间若能被两个小区间覆盖,那么大区间的最值等于两个小区间的最值。
区间可以有重合,不影响结果。如此一来,基本思路就是:
- 把一个整数列分为很多个小区间,并提前计算出小区间的最值
- 对任意区间最值查询,找到覆盖它的两个小区间,由两个小区间的最值算出答案。
其中第一步对应着预处理,第二步对应着查询。
预处理:
按照长度1,2,4,……来划分小区间(倍增),如下图所示:
可以发现,每个小区间的最小值可有前一组的两个小区间推出。例如,第2组的$\{ 9,3\}$最小值可由第1组的$\{9\},\{ 3\}$两边的最小值得出;第3组的$\{9,3,2,1\}$最小值可由$\{9,3\},\{2,1\}$两边的最小值得出。所以这就是一个DP的过程。
采用二维数组
$$ f[i][j] $$
来表示从索引 $i$ 开始长度为 $2^j$ 的区间的最值。预处理过程的时间复杂度为 $O(n\log n)$。
预处理阶段采用动态规划来填充表。对于每个表元素,通过比较两个相邻的长度为 $2^{j-1}$ 的区间最值得到。以求最大值为例,有
$$ f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1]) $$
于是每组在 $O(n)$ 时间内算出所有子区间的最值。
查询:当查询某一区间 $[L,R]$ 的最值时,将其拆分为两个小区间,且这两个小区间属于同一组。以$L$为起点的小区间和以$R$为终点的小区间,让这两个小区间首尾相接覆盖 $[L,R]$ 区间。
两个区间长度$x$,为比大区间长度小的最大的2的倍数,那么有$x\le len且2x\ge len$,这样才能保证两个小区间覆盖大区间。对于第k组,有$2^k=x$,所以
$$ k=\log_2(R-L+1)=\log_{10}(R-L+1)/\log_{10}(2) $$
有查询结果为
$$ max(f[L][k],f[R-(1<<k)+1][k]) $$
其中对应了以 $L$ 开头的左区间和以 $R$ 结尾的右区间。
最终代码如下:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 200020,M=18;
int n,m;
int a[N];
int f[N][M];
void init(){
for(int j=0;j<M;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
if(!j) f[i][j]=a[i];
else f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int query(int l,int r){
int len = r- l + 1;
int k=log(len)/log(2);
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
init();
scanf("%d",&m);
while(m--){
int l,r;
scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}
return 0;
}
线段树单次查询时间复杂度O(logn),总的复杂度就是O(mlogn)。
谢谢已经改了