1305: 老管家的忠诚(ST表)

解题思路:ST表预处理时间为o(nlogn),查询时间为o(1),适用于区间最值查询,但不支持在线修改

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
int F[100005][30];
int n;
int a[100005];
void ST_create()
{
	for(int i=1;i<=n;i++)
	{
		F[i][0]=a[i];
	}
	int k=log2(n);
	for(int j=1;j<=k;j++)
	{
		for(int i=1;i<=n-(1<<j)+1;i++)
		{
			F[i][j]=min(F[i][j-1],F[i+(1<<(j-1))][j-1]);
		}
	}
}
int ST_query(int l,int r)
{
	int k=log2(r-l+1);
	return min(F[l][k],F[r-(1<<k)+1][k]);
} 
int main()
{
	int T;
	scanf("%d%d",&n,&T);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	ST_create();
	while(T--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d ",ST_query(l,r));
	}
	return 0;	
}