void init(){    for (int i = 0; i < n; i++) st[i][0] = a[i];    for (int j = 1; (1 << j) <= n; j++){        for (int i = 0; i + (1 << j) - 1 < n; i++){            st[i][j] = min(st[i + (1 << (j-1))][j - 1], st[i][j - 1]);        }    }}inline int query(int l, int r){    int len = r - l + 1;    int k = 0;    while ((1 << (k + 1)) <= len) k++;    return min(st[l][k], st[r - (1 << k) + 1][k]);}

 

 

二维：

定义dp(i, j, k, L)表示以(i,j)为左上角，宽度为(2^k, 2^L)的区间内的某个数值

int dp[maxn][maxn][8][8], dp2[maxn][maxn][8][8];void init_st(){    for (int i = 0; (1 << i) <= n; i++){        for (int j = 0; (1 << j) <= n; j++){            if (i == 0 && j == 0) continue;            for (int x = 1; x + (1 << i) - 1 <= n; x++){                for (int y = 1; y + (1 << j) - 1 <= n; y++){                    if (i == 0) {                        dp[x][y][i][j] = min(dp[x][y][i][j - 1], dp[x][y + (1 << (j - 1))][i][j - 1]);                        dp2[x][y][i][j] = max(dp2[x][y][i][j - 1], dp2[x][y + (1 << (j - 1))][i][j - 1]);                    }                    else {                        dp[x][y][i][j] = min(dp[x][y][i - 1][j], dp[x + (1 << (i - 1))][y][i - 1][j]);                        dp2[x][y][i][j] = max(dp2[x][y][i - 1][j], dp2[x + (1 << (i - 1))][y][i - 1][j]);                    }                }            }        }    }}int query(int x, int y, int X, int Y){    int maxi = 0, mini = 1e8;    int k1 = 0, k2 = 0;    while (1 << (1 + k1) <= X - x) k1++;    while (1 << (1 + k2) <= Y - y) k2++;    maxi = max(maxi, max(dp2[x][y][k1][k2], dp2[X - (1 << k1) + 1][y][k1][k2]));    maxi = max(maxi, max(dp2[x][Y - (1 << k2) + 1][k1][k2], dp2[X - (1 << k1) + 1][Y - (1 << k2) + 1][k1][k2]));    mini = min(mini, min(dp[x][y][k1][k2], dp[X - (1 << k1) + 1][y][k1][k2]));    mini = min(mini, min(dp[x][Y - (1 << k2) + 1][k1][k2], dp[X - (1 << k1) + 1][Y - (1 << k2) + 1][k1][k2]));    //printf("maxi = %d mini = %d\n", maxi, mini);    return maxi - mini;}