RMQ之ＳＴ求区间最大值

题目链接：https://cn.vjudge.net/problem/HRBUST-1188

每一次按照二进制的方式进行更新，二维数组dp [i] [j],i表示下标，ｊ表示从i 开始的往后移动２的ｊ－１次方个数再－１．

ＡＣ代码：

 1 #include<iostream>
 2 #include<cmath>
 3 #include<stack>
 4 #include<iomanip>
 5 #include<queue>
 6 #include<cstring>
 7 #include<string>
 8 #include<stdio.h>
 9 #include<algorithm>
10 #include<vector>
11 using namespace std;
12 # define inf 0x3f3f3f3f
13 # define ll long long
14 const int maxn = 50000+100;
15 int dp[maxn][20];
16 int n;
17 void RMQ()
18 {
19     for(int i=1; i<=20; i++)
20     {
21         for(int j=1; j<=n; j++)
22         {
23             if(j+(1<<i)-1<=n)
24             {
25                 dp[j][i]=max(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
26             }
27         }
28     }
29 }
30 int main()
31 {
32 
33     int Case=0;
34     while(~scanf("%d",&n))
35     {
36         memset(dp,0,sizeof(dp));
37         for(int i=1; i<=n; i++)
38         {
39             scanf("%d",&dp[i][0]);
40         }
41         RMQ();
42         int m;
43         int t1,t2;
44         scanf("%d",&m);
45         printf("Case %d:
",++Case);
46         while(m--)
47         {
48             scanf("%d%d",&t1,&t2);
49             int k=0;
50           // k=(int)(log((double)(t2-t1+1))/log(2.0));
51            while((t1+1<<(k+1))<=t2)k++;
52             printf("%d
",max(dp[t1][k],dp[t2-(1<<k)+1][k]));
53         }
54     }
55     return 0;
56 }
57