可以用来解决RMQ（区间最值）等可重复贡献问题^[1]。

引入：

对于RMQ问题，我们通常有这几种方法处理：

1. 朴素（即搜索）(O(nm))

2. 打表 (O(n^2))

3. ST表 (O(nlogn))

4. 线段树 (O(nlogn))

我们比较容易想到用打表的方法，也就是比较简单的dp，像这样：
定义 (ans[i][j]) 表示区间 ([i,j]) 的最值

(begin{cases}
ans[i][j] = a[i] , i = j\\
ans[i][j] = max(ans[i][j-1], a[j])
end{cases})

可是这样的空间复杂度 (O(n^2)) 时间复杂度 (O(n^2)) 不是很令人满意，所以我们考虑用ST表来处理静态(mathrm{(offline)})的RMQ问题。

分析：

要求解一个区间的最值，ST表用了类似区间dp的方法。
(dp[i][j]) 表示的是从 (i) 开始，长度为 (2^j) 的区间中的最值。也就是区间 ([i,2^j+i-1]) 的最值。

对于每一次询问，我们可以通过 (l) 和 (r) 算得区间的长度 (len) ，然后计算 $$j = lfloor log_{2}{len} rfloor$$ 最大值就是 $$max(dp[l][j], dp[r-2^j+1][j])$$
就像这样：

就是在这两段有重叠部分的区间取其中的最大值，重叠并不会影响 ([l,r]) 区间的最大值。

预处理：

首先，当区间长度为0时，区间的最值就是区间端点的值。即 (dp[i][0] = a[i])

然后开始类似区间dp的处理方法。

先枚举区间长度，再枚举区间端点。

这里的 (j-1) 相当于将区间对半分，整个的最值等于左边和右边取最值。
代码：

for (int j = 1; j <= log2(n); j++)
    for (int i = 0; i + (1 << j) - 1 < n; i++)
        dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);

查询：

和分析中说的一样
代码：

int query(int l, int r)
{
    int j = (int)log2(r - l + 1);
    return max(dp[l][j], dp[r - (1 << j) + 1][j]);
}

例题：

• 洛谷 P3865 【模板】ST 表

模板代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int log2N = 17; //这是计算得到的log2(N)
int dp[N][log2N]; //dp[i][j] 表示左端点为 i 区间长度为 2^j 的区间中的最大值，即区间[i,i+2^j-1]
int query(int l, int r)
{
    int t = r - l + 1;
    int j = (int)log2(t);
    return max(dp[l][j], dp[r - (1 << j) + 1][j]);
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &dp[i][0]);
    for (int j = 1; j <= log2(n); j++)
        for (int i = 0; i + (1 << j) - 1 < n; i++)
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);

    int l, r;
    while (m--)
    {
        scanf("%d%d", &l, &r);
        printf("%dn", query(l - 1, r - 1));
    }
}