ST表是一种求区间最值的高效数据结构，不支持动态维护，建表时间复杂度O(nlogn)，查询复杂度O(1)。在不需要修改原数据的情况下ST表要比线段树更简洁，但在需要修改原数据时只能用线段树。

        ST表可以定义为二维数组ST[][]，其中ST[i][j]表示从第j的元素开始的长度为2i的区间中的最值，也就是区间[j，j+2i-1]中的最值。这个表可以用DP思想建立。
        建表前，需要两个辅助数组log[]与bin[]。其中log[i]储存使2k<=i的整数k的最大值;bin[i]储存2i。这两个数组都可以通过递推实现:

        log数组大小达到数据量n，bin达到logn。
        辅助数组构建完毕后开始建ST表。首先对ST表首行初始化，即ST[0][x]。它们都表示从x号元素开始长度为1的区间的最值，显然就是该元素本身。
        此外ST表中有递推公式:

        即将区间分成两半，求取其中的最值，这里注意x+bin[i]-1≤n。递推后即可完成建表。

下面探讨查询操作。
        其实也可以用将区间平均拆分的分治思想来求给定区间的最值，但是给定区间长度不一定就是2的方幂，于是需要其它分治方法。
        注意到有不等式2log[l]*2>l。这是显然的。这个不等式启示我们可以将长度为l的区间拆分成两个长度为2log[l]的区间，这两个区间已然覆盖了区间所有的值。
        因此区间[a，b]的最值即为$\max/\min\{ST[log[l]][a]，ST[log[l]][b-bin[log[l]]+1]\}$。
        这里l=b-a+1，为区间长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>

using namespace std;
int ST[20][10000];//储存ST表数据
int op[10000], n;//储存区间数据
int log[10000], bin[20];//储存log值以及指数值
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> op[i];
        ST[0][i] = op[i];
    }//第一行初始化
    log[0] = -1;
    for (int i = 1; i <= n; i++)log[i] = log[i / 2] + 1;//log初始化
    bin[0] = 1;
    for (int i = 1; i < 20; i++)bin[i] = bin[i - 1] * 2;//bin初始化
    for (int i = 1; i < 20; i++) {
        for (int j = 1; j <= n; j++) {
            if (j + bin[i] - 1 <= n) {
                ST[i][j] = min(ST[i - 1][j], ST[i - 1][j + bin[i - 1]]);//递推建表,DP思想
            }
        }
    }
    int k;
    cin >> k;//查询k次
    while (k-- > 0) {
        int l, r;
        cin >> l >> r;
        int t = log[r - l + 1];
        cout << min(ST[t][l], ST[t][r - bin[t] + 1]) << endl;//输出查询结果
    }
    return 0;
}