ST表可以实现静态数据查询

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N][20];
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i][0]);
    }
    int Len = log(n) / log(2) + 1;
    for(int j = 1; j < Len; j++){
        for(int i = 1; i <= n - (1 << j) + 1; i++){
            a[i][j] = max(a[i][j-1], a[i+(1<<j-1)][j-1]);
        }
    }
    int m;
    scanf("%d", &m);
    while(m--){
        int x, y;
        scanf("%d %d", &x, &y);
        int t = log(y - x + 1) / log(2);
        printf("%d\n", max(a[x][t], a[y-(1<<t)+1][t]));
    }
    return 0;
}

BIT树可以实现动态数据查询

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N], ma[N];
int n;
inline int lowbit(int x){
    return x & -x;
}
void add(int x, int v){
    for(; x <= n; x += lowbit(x)){
        ma[x] = max(ma[x], v);
    }
}
int query(int x, int y){
    int ret = a[y];
    while(y >= x){
        if(y - lowbit(y) + 1 >= x){
            ret = max(ret, ma[y]);
            y -= lowbit(y);
        }else{
            ret = max(ret, a[y]);
            y--;
        }
    }
    return ret;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        ma[i] = -INT_MAX;
    }
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        add(i, a[i]);
    }
    int m;
    scanf("%d", &m);
    while(m--){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%d\n", query(x, y));
    }
    return 0;
}