ST表（动态规划倍增思路离线维护区间极值问题）

Acwing

$Code:$

#include<bits/stdc++.h>
#include<unordered_map>
#define debug cout << "debug--- "
#define debug_ cout << "\n---debug---\n"
#define oper(a) operator<(const a& ee)const
#define forr(a,b,c) for(int a=b;a<=c;a++)
#define mem(a,b) memset(a,b,sizeof a)
#define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0))
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define endl "\n"
#define ul (u << 1)
#define ur (u << 1 | 1)
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll, int> PII;

const int N = 2e5 + 10, M = 2e3 + 10, mod = 1e9 + 7;
int INF = 0x3f3f3f3f; ll LNF = 0x3f3f3f3f3f3f3f3f;
int n, m, B = 10, ki;

int f[N][18], a[N];
int lg[N];//预处理log2(N)是多少，可以加速很多 

void init() {
    
    //倍增动态规划
    //f[i][j]维护 i 点开始长度为 2^j 段的最大值
    for (int j = 0; j < 18; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            if (!j)f[i][j] = a[i];
            else f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

int query(int l, int r) {
    
    int len = r - l + 1;
    int k = lg[len];
    return max(f[l][k], f[r - (1 << k) + 1][k]);

    //找一个最大的不会超过长度（下取整）的次方数 k
    //前后两段取极值，包含了区间
}

void solve() {
    
    cin >> n;
    lg[0] = -1;
    forr(i, 1, n)cin >> a[i], lg[i] = lg[i >> 1] + 1;//递推
    init();

    cin >> m;
    while (m--)
    {
    
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << endl;
    }
}

int main() {
    
    cinios;
    int T = 1;
    for (int t = 1; t <= T; t++) {
    
        solve();
    }
    return 0;
}
/* */