ST表是利用倍增思想处理RMQ问题（区间最值问题）的一种工具。 它能够做到O(nlogn)预处理，O(1)查询的时间复杂度，效率相当不错。
ST表利用倍增的思想。以洛谷的P3865作为例子。我们需要查询某一区间的最大值。 我们用f[ i ][ j ]表示区间i到i+2^j-1的最大值（最小值同理）。在状态转移时，我们可以把这个区间拆成两个区间，分别求最大值。 
因此，状态转移方程为：
f[i][j] = max{ f[i][j-1], f[i+2^(j-1)][j-1] }
查询也比较简单。 我们先求出log2(区间长度),令其等于k。 
然后，我们对左右端点分别查询（即图中的绿色线条和红色线条），保证能够覆盖我们需要查询的整个区间。
为什么从右端点开始查询，左端点为r-2^k+1？ 其实很简单，我们需要寻找一个x，使得x+2^k-1=r。所以x=r-2^k+1。
上代码：
//ST表求静态区间最大值 洛谷P3865 #include <iostream> #include <cstdio> #include <cmath> using namespace std; const int maxn=1e6+10; int n,m; int Max[maxn][21];//Max[i][j]表示区间i到i+2^j-1的最大值 int read() { char ch=getchar(); int f=1;int x=0; 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 find(int l,int r) { int k=log2(r-l+1);//计算log2(区间长度) return max(Max[l][k],Max[r-(1<<k)+1][k]); } int main() { n=read();m=read(); for(int i=1;i<=n;i++) { Max[i][0]=read(); } for(int j=1;j<=21;j++) { for(int i=1;i+(1<<j)-1<=n;i++) { Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]); //倍增 //1<<(j-1)表示2^(j-1) } } for(int i=1;i<=m;i++) { int l=read(); int r=read(); printf("%d\n",find(l,r)); } return 0; }
原文：https://www.cnblogs.com/Bw-Orzzzzz/p/10829036.html