双ST表

做两个ST表，都是用来查最大的，只是一个查正数，一个查相反数(等价正数最小)，最后相加即可

#include <iostream>
#include<cmath>
#include<algorithm>
using namespace std;

const int MAXN = 1e5+1;
int f[MAXN][100],a[MAXN],f2[MAXN][100];
int n,m;

void ST_prework(){                           //正数ST表
    for(int i = 1; i <= n ; i ++){
        f[i][0] = a[i];
    }

    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; j++){
        for (int i = 1; i <= n - (1 << j)+1; i++){
            f[i][j] = max(f[i][j - 1],f[i + (1 << (j-1))][j-1]);
        }
    }
}

void ST2_prework(){                            //负数ST表
    for(int i = 1; i <= n ; i ++){
        f2[i][0] = -1*a[i];
    }

    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; j++){
        for (int i = 1; i <= n - (1 << j)+1; i++){
            f2[i][j] = max(f2[i][j - 1],f2[i + (1 << (j-1))][j-1]);
        }
    }
}

int ST_query(int l , int r){
    int k = log(r - l + 1) / log(2);
    return max(f[l][k],f[r - (1<<k) + 1][k]);
}

int ST2_query(int l , int r){
    int k = log(r - l + 1) / log(2);
    return max(f2[l][k],f2[r - (1<<k) + 1][k]);
}

int main(int argc, char* argv[]) {
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i ++){
        scanf("%d",a+i);
    }

    ST_prework();
    ST2_prework();

    for(int i = 1; i <= m; i ++){
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d\n",abs(ST_query(x,y)+ST2_query(x,y)));       //正负相加即可
    }

    return 0;
}