ST表首先预处理了一部分的区间最大值，处理的部分的左端点为数组的每个点，长度为的所有区间，个数就是个，查询时将查询的区间分成可能有重叠的两部分，查询的值就是这两部分的最大值，

 分成的两部分的长度均为，这样两部分就都可以直接查询，

具体实现：

const int N = 1e5 + 7;
int f[N][18];
int a[N];
int n, m;
int getmax(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);
    return max(f[l][k], f[r + 1 - (1 << k)][k]);
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int j = 0; j < 18; j++)
    {
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            if (j == 0)
                f[i][j] = a[i];
            else
                f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
    }
    int x, y;
    while (m--)
    {
        cin >> x >> y;
        cout << getmax(x, y) << endl;
    }
}

 

举个例子，假设要查询区间 [5，11] 中的最大值时查询[5，9]和[7，11]的最大值就可以了，而二者即为预处理过的st[5][2]，st[7][2]，这样就做到了O(1)的查询。

查询最小值时只需要将代码中的max全部换为min即可。

例题： 1270. 数列区间最大值 - AcWing题库

同样的题目使用线段树可能也能通过，线段树的更新和查找都是，建树是,所以总复杂度就是，

而ST表是的复杂度，并且常数小得多，代码短，但是不支持动态修改，总之各有优点。

同时吹爆AcWing，y总nb