数列区间最大值（ST表）

标签：begin ch end 数列 max 最大值 ST right aligned

预处理部分

\[\max(a[i,i+2^k-1]) =\max \left\{ \begin{aligned} \max&(a[i,i+2^{k-1}-1])\\ \max&(a[i+2^{k-1},i+2^{k-1}+2^{k-1}-1]) \end{aligned} \right.= \left\{ \begin{aligned} \max&(a[i,i+2^{k-1}-1])\\ \max&(a[i+2^{k-1},i+2^k-1]) \end{aligned} \right.= \max(a[i,i+2^k-1]) \]

查询部分

\[p=\lfloor \log_{2}{(l+r-1)} \rfloor \]

\[\max(a[l,r]) = \max \left\{ \begin{aligned} \max&(a[l,l^p-1])\\ \max&(a[r-2^p+1,r-2^p+1+2^p-1]) \end{aligned} \right. = \max \left\{ \begin{aligned} \max&(a[l,l^p-1])\\ \max&(a[r-2^p+1,r]) \end{aligned} \right. \]

代码

#include<cstdio>
#define max(x,y) (x)>(y)?(x):(y)
using namespace std;

inline int read()
{
	int x=0;bool w=true;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=false;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
	return w?x:-x;
}

const int N=1e5+5,Q=1e6+5;
int n,q;

int lg2[N],f[N][25];
inline void ST_Init()
{
	for(int i=2;i<=n;i++)
		lg2[i]=lg2[i>>1]+1;
	for(int k=1;k<=lg2[n];k++)
		for(int i=1;i+(1<<k)-1<=n;i++)
			f[i][k]=max(f[i][k-1],f[i+(1<<k-1)][k-1]);
	//max(a[i,i+2^k-1])=max(max(a[i,i+2^(k-1)-1]),max(a[i+2^(k-1),i+2^(k-1)+2^(k-1)-1=i+2^k-1]))
	return;
}
inline int ST_query(const int l,const int r)
{
	int p=lg2[r-l+1];
	return max(f[l][p],f[r-(1<<p)+1][p]);
}

int main()
{
	n=read(),q=read();
	for(int i=1;i<=n;i++)
		f[i][0]=read();
	ST_Init();
	for(int i=1;i<=q;i++)
	{
		int x=read(),y=read();
		printf("%d\n",ST_query(x,y)); 
	}
	return 0;
}

标签：begin,ch,end,数列,max,最大值,ST,right,aligned
From： https://www.cnblogs.com/jerrycyx/p/18342706