前往：我自己搭建的博客
题目
洛谷P3865 ST表
题解
ST表适用于数据量较小，查询量较大的静态区间最值问题（RMQ问题）。
1.预处理
设f[i][j]为区间[i,i+2^j-1]内的最值，利用动态规划的思想，f[i][j]可以由f[][j-1]更新而来。
由于自带的log2()函数效率较低，所以需要自行递推，设lg2[n]表示log2(n)向下取整，则lg2[n]=lg2[n/2]+1。
2.询问
若要查询[l,r]内的最值，先要找到最大的x，使2^x<=r-l+1，然后取从左右端点l,r出发的两个长度为2^x的区间的最值的最值。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m;
int f[maxn][20],lg2[maxn];
inline int read()
{
int s=0; char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
return s;
}
inline void get_ST()
{
for(int i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;
for(int i=1;i<=n;i++) f[i][0]=read();
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
inline int RMQ(int l,int r) {int t=lg2[r-l+1]; return max(f[l][t],f[r-(1<<t)+1][t]);}
int main()
{
n=read(),m=read(); get_ST();
for(int i=1;i<=m;i++) {int l=read(),r=read(); printf("%d\n",RMQ(l,r));}
return 0;
}
