区间静态询问最值，倍增数组ST表

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+10;
int a[N][20], b[N][20];
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i][0]);
        b[i][0] = a[i][0];
    }

    int len = log(n) / log(2) + 1;
    for(int i = 1; i <= len; i++){
        for(int j = 1; j <= n - (1<<i) + 1; j++){
            a[j][i] = max(a[j][i-1], a[j+(1<<i-1)][i-1]);
            b[j][i] = min(b[j][i-1], b[j+(1<<i-1)][i-1]);
        }
    }

    while(m--){
        int ll, rr;
        scanf("%d %d", &ll, &rr);
        int t = log(rr - ll + 1) / log(2);
        int ma = max(a[ll][t], a[rr-(1<<t)+1][t]);
        int mi = min(b[ll][t], b[rr-(1<<t)+1][t]);
        printf("%d\n", ma - mi);
    }
    return 0;
}

区间静态询问最值，树状数组解决（可以解决动态问题）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N], ma[N], mi[N]; //原始、树状 
int n, m;
inline int lowbit(int x){
    return x & -x;
}
void addma(int x, int v){
    for(;x <= n; x += lowbit(x)){
        ma[x] = max(ma[x], v);
    }
}
void addmi(int x, int v){
    for(;x <= n; x += lowbit(x)){
        mi[x] = min(mi[x], v);
    }
}
int queryma(int x, int y){
    int ret = 0;
    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 querymi(int x, int y){
    int ret = a[y];
    while(y >= x){
        if(y - lowbit(y) + 1 >= x){
            ret = min(ret, mi[y]);
            y -= lowbit(y);
        }else{
            ret = min(ret, a[y]);
            y--;
        }
    }
    return ret;
}
int main(){
    scanf("%d %d", &n, &m);
    memset(mi, 0x3f, sizeof(mi));
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        addma(i, a[i]);
        addmi(i, a[i]);
    }
    while(m--){
        int ll, rr;
        scanf("%d %d", &ll, &rr);
        printf("%d\n", queryma(ll, rr) - querymi(ll, rr));
    }
    return 0;
}