这是一道ST表经典题——静态区间最大值
请注意最大数据时限只有0.8s，数据强度不低，请务必保证你的每次查询复杂度为 O(1)
给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。
输入格式：
第一行包含两个整数 N, M，分别表示数列的长度和询问的个数。
第二行包含 N 个整数（记为 ai?），依次表示数列的第 i 项。
接下来 M 行，每行包含两个整数 li?,ri?，表示查询的区间为[li?,ri?]
输出格式：
输出包含 M行，每行一个整数，依次表示每一次询问的结果。
输入样例1：
8 8 9 3 1 7 5 6 0 8 1 6 1 5 2 7 2 6 1 8 4 8 3 7 1 8
输出样例1：
9 9 7 7 9 8 7 9
对于30%的数据，满足： 1≤N,M≤10
对于70%的数据，满足： 1≤N,M≤105
对于100%的数据，满足： 1≤N≤105,1≤M≤106,ai?∈[0,109],1≤li?≤ri?≤N
思路：by自为风月马前卒
ST表是利用的是倍增的思想，拿最大值来说，我们用Max[i][j]表示，从i位置开始的2j个数中的最大值，例如Max[i][1]表示的是i位置和i+1位置中两个数的最大值
那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值（注意这里的编号是从1开始的）
查询的时候也比较简单，我们计算出log2(区间长度)，然后对于左端点和右端点分别进行查询，这样可以保证一定可以覆盖查询的区间
刚开始学的时候我不太理解为什么从右端点开始查的时候左端点是r−2k+1。实际很简单，因为我们需要找到一个点x，使得x+2k−1=r，这样的话就可以得到x=r−2k+1
代码：
#include<cstdio> #include<algorithm> #include<iostream> #include<cmath> using namespace std; static int n,m; static int st[1000008][21];//建立倍增ST 域:[n][log2(n)] static int l,r,k; long long read() { long long x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int main() { n=read();m=read(); for(int i=1;i<=n;++i) st[i][0]=read();//表示从i到i+2^j-1的值 为i本身 for(int j=1;j<=21;++j)//ST域 for(int i=1;i+(1<<j)-1<=n;++i)//i的取值范围是根据i后面还有2的几次方个数算的 st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);//理论 for(int i=1;i<=m;++i) { l=read();r=read(); k=log2(r-l+1);//寻找一个k使得其覆盖整个查询区间 printf("%d\n",max(st[l][k],st[r-(1<<k)+1][k]));//理论 可以覆盖 } return 0; }
原文：https://www.cnblogs.com/-hhs/p/11107072.html