http://blog.csdn.net/insistgogo/article/details/9929103
这篇博客讲解的很详细了，求区间最大值也可以用st表，时间复杂度O（n log（n）），查询复杂度O（1）
主要是用到区间动规 的思想（虽然我不会区间动规= =）
在求解rmq问题时，st表是很有用的
-------------------------**********************-------------------------------------
要注意的是st表只能离线处理，要在线处理必须要用树状数组或者线段树
-------------------------**********************--------------------------------------
一道模板题lightoj1082
#include<map> #include<set> #include<cmath> #include<queue> #include<stack> #include<vector> #include<cstdio> #include<cassert> #include<iomanip> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define C 0.5772156649 #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-7; const int N=100000+10,maxn=500+100,inf=0x3f3f3f; int st[N][32]; int n; void init() { for(int i=1;(1<<i)<=n;i++) for(int j=1;j<=n-(1<<i)+1;j++) st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]); } int get(int l,int r) { int s=log2(r-l+1); return min(st[l][s],st[r-(1<<s)+1][s]); } int main() { /*ios::sync_with_stdio(false); cin.tie(0);*/ int t,m,cnt=0; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++)scanf("%d",&st[i][0]); init(); printf("Case %d: ",++cnt); while(m--) { int a,b; scanf("%d%d",&a,&b); printf("%d ",get(a,b)); } } return 0; } /******************** 5 1 5 3 4 2 ********************/