倍增算法

倍增算法

RMQ（区间最值查询）
主要思想就是区间dp出每个点起2的k次方的长度内的极值。运用大区间的极值由小区间得到，同时大区间的答案可以由小区间随意组合得到。比如我们已经预处理1为起点长度为4的答案，和2为起点向后4的答案，我们查询区间1到5的极值就可以比较1-4区间和2-5区间的答案来得到1-5的答案
二维DP数组：ST表
ST表数组：f[i][j]，表示区间【i，i+2j-1】的最大值。这个区间的大小是2j个数。
ST表的初始化：f[i][0]=a[i]。（显然这是区间大小为1的时候）
ST表的递推过程：

1. 由区间大小为1的项转移得到区间大小为21的项
2. 由区间为21的项转移得到区间为22的项
3. 由区间为22的项转移得到区间为23的项

/*
在递推时，把子区间的长度成倍增长
另F[i,j]表示数列A中下标在子区间[i,i+2^j-1]里的数的最大值
F[i,j]=max(F[i,j-1],F[i+2^j-1,j-1]) 
*/
#include<iostream>
#include<algorithm>
#include<cmath>
//log函数 
using namespace std;
int f[10000][100];
int a[10000];
int N;
//预处理 
void ST_prework()
{
	for(int i=1;i<=N;i++)
		f[i][0]=a[i];
	int t=log(N)/log(2)+1; //log2N
	for(int j=1;j<t;j++)
	{
		for(int i=1;i<=N-(i<<j)+1;i++)
		{
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
}
int ST_query(int l,int r)
{
	int k=log(r-l+1)/log(2);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
	cin>>N;
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=N;i++)
		cin>>a[i];
	cout<<ST_query(n,m)<<endl;
	return 0;
}