分别写了下标从0和1开始的两种
1 #include<stdio.h>
2 #include<string.h>
3 #include<algorithm>
4 #include<math.h>
5 using namespace std;
6
7 const int maxn=1e5+5;
8 const int maxl=20;
9
10 int ma[maxn][maxl];
11 int st[maxn][maxl];
12 int a[maxn],prelog[maxn];
13
14 void initRMQ(int n){
15 for(int i=2;i<=n;++i){
16 prelog[i]=prelog[i-1];
17 if((i&(-i))==i)prelog[i]++;
18 }
19 for(int i=1;i<=n;++i)ma[i][0]=a[i];
20 for(int j=1;(1<<j)<=n;++j){
21 for(int i=1;i+(1<<j)-1<=n;++i){
22 ma[i][j]=max(ma[i][j-1],ma[i+(1<<j-1)][j-1]);
23 }
24 }
25 }
26
27 int askRMQ(int l,int r){
28 if(l>r)swap(l,r);
29 int k=prelog[r-l+1];
30 return max(ma[l][k],ma[r-(1<<k)+1][k]);
31 }
32
33
34 void initST(int n){
35 for(int i=2;i<=n;++i){
36 prelog[i]=prelog[i-1];
37 if((1<<prelog[i]+1)==i)++prelog[i];
38 }
39 for(int i=0;i<n;++i)st[i][0]=a[i];
40 for(int i=n-1;i>=0;--i){
41 for(int j=1;i+(1<<j)-1<n;++j){
42 st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
43 }
44 }
45 }
46
47 int askST(int l,int r){
48 if(l>r)swap(l,r);
49 int k=prelog[r-l+1];
50 return max(st[l][k],st[r-(1<<k)+1][k]);
51 }