-ST表模板

 ST表用于快速查询区间最大值

//用于寻找区间最大值
//ST模板

#include<bits/stdc++.h>
using namespace std;
#define N 100009
int a[N][30];
int n;
int b[N];
int max(int o,int p){
	if(o>p){
		return o;
	}
	return p;
}
void init(){
	int i=0,j=0;
	for(i=1;i<=n;i++){
		a[i][0]=b[i];
	}
	for(i=1;(1<<i)<=n;i++){
		for(j=1;j+(1<<i)<=n+1;j++){
			a[j][i]=max(a[j][i-1],a[j+(1<<(i-1))][i-1]);
		}
	}
}
int search(int l,int r){
	int k=log(r-l+1)/log(2);
	int t=max(a[l][k],a[r-(1<<k)+1][k]);
	return t;
}
int main()
{	
	int m;
	scanf("%d %d",&n,&m);
	int i=0;
	for(i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	int x,y;
	init();
	for(i=1;i<=m;i++){
		scanf("%d %d",&x,&y);
		int end=search(x,y);//x，y表示的是每次查询的左右区间
		printf("%d\n",end);
	}
	return 0;
}

ST表的一道模板题

【模板】ST 表 - 洛谷