给一个数列，巨多次询问区间最值，窝萌用ST表解决多次查询不修改问题。这篇以左闭右闭区间为例。
st [ i ] [ j ] 表示从第 i 位开始 ( 包括第 i 位 ) ，2 ^ j 个数中的最值。
显然，st [ i ] [ 0 ] = n [ i ] st [ i ] [ j ] = max ( st [ i ] [ j - 1 ] , st [ i + 2^( j - 1) ] [ j - 1 ] )
在预处理时，由于需要用到st [ i + 2^( j - 1) ] [ j - 1 ]，必须把 j 作为外层循环，否则st [ i + 2^( j - 1) ] [ j - 1 ]全是0。
预处理好了之后，窝萌就可以 O ( 1 ) 地查询区间最值 (rmq) 了。
我们发现这样一个性质 : max ( L ~ R ) = max ( max( L ~ i ) , max( j ~ R ) ) ( L ≤ j ≤ i ≤ R )
利用窝萌预处理好的st表，取 m = log2 ( R - L + 1 )，易知max ( L ~ R ) = max ( st [ L ] [ m ] , st [ R - 2^m + 1] [ m ] ) （开篇说明是左闭右闭区间，其他情况注意边界+1-1即可）
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int n[100005]; int a; int st[100005][25]; //st[i][j]表示从第 i项开始(包含第 i项)，2^j 项中的最值 void init() { for(int i=1;i<=a;i++) st[i][0]=n[i]; for(int j=1;j<=20;j++) //一定是表示 2^j 的循环在外层 //1e5 ~ 2^17 1e6 ~ 2^20 for(int i=1;i+(1<<j)-1<=a;i++) st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]); } void find(int ll,int rr) { int mid=log2(rr-ll+1); int ans=max(st[ll][mid],st[rr-(1<<mid)+1][mid]); printf("%d\n",ans); } int main() { int m; scanf("%d%d",&a,&m); for(int i=1;i<=a;i++) scanf("%d",&n[i]); init(); int l,r; for(int i=1;i<=m;i++) { scanf("%d%d",&l,&r); find(l,r); } return 0; }
原文：https://www.cnblogs.com/nightfury/p/14408659.html
