ST表

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1e5+9;
 4 
 5 int n,m;
 6 int a[N];
 7 int f[N][30];//表示 从第i个数开始（包括第i个）走2j个数的一个区间
 8 
 9 int main (){
10     std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
11     cin >> n >> m;
12     for(int i=1;i<=n;i++){
13         cin >> a[i];
14     }
15     for(int i=1;i<=n;i++) f[i][0] = a[i];//第i个数走2的0次方就是它本身
16     for(int j=1;j<=20;j++){//因为是走2的j次方，所以20就差不多够大了
17         for(int i=1;i+(1<<j)-1<=n;i++){//设置边界，即从第i个数走过2的j次方个数后 不能超过数的总个数
18             f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);//i~i+(1<<j)这个区间由两个组成。i走2j-1个数是一个区间，i+2j-1再走2j-1个数是另一个区间，这两个小区间的的最大值就是整个大区间的最值
19         }
20     }
21     int l,r;
22     for(int i=1;i<=m;i++){
23         cin >> l >> r;
24         int k = log2(r-l+1);//   2k <= log2(r-l+1) < 2k+1，所以可以算出k，用k来覆盖区间
25         cout << max(f[l][k],f[r-(1<<k)+1][k]) << "\n";//左区间由l开始走2k个数，右区间由r和k倒推起点
26     }
27     return 0;
28 }