[C++知识库]RMQ（ST表）

作用：可以静态查询区间[l,r]，但是不支持修改区间里的值。

1273. 天才的记忆

题意：给定一组数，查询任意区间[l,r]里的最大值。

思路：f[i][j]表示从i开始，长度为2^j的区间里的最大值，对区间长度二分则
f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]),长度2^j/2=2^(j-1)，所以可以预处理出所有的f[i][j]；
[l,r]怎么表示，len=r-l+1，2^k=len，求出k，此时的k可能2^k<len，所以可以分成
两部分f[l][k],l[r-2^k+1][k]，可保证一定覆盖了[l,r]这整个区间。

#include<iostream>
#include<cmath>
using namespace std;
const int N=2e5+10,M=20;
int f[N][M],a[N];
int n,m;
void init()
{
	for(int len=0;len<M;len++)
	{
		for(int i=1;i+(1<<len)-1<=n;i++)//i+(1<<len)-1终点不能越界
		{

			if(len==0) f[i][len]=a[i];//长度为2^0=1
			else f[i][len]=max(f[i][len-1],f[i+(1<<(len-1))][len-1]);
		}
	}
}
int query(int l,int r)
{
	int len=r-l+1;
	int k=log(1.0*len)/log(1.0*2);//换底公式
	return max(f[l][k],f[r-(1<<k)+1][k]);//f[1+1<<k][k]是不行的，可能会超过[l,r]的范围
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	init();
	cin>>m;
	while(m--)
	{
		int l,r;
		cin>>l>>r;
		cout<<query(l,r)<<endl;
	}
	return 0;
}