初识st表-P2880

首先讲讲 st 表。这个东西呢，就是一种利用了倍增思想的预处理数据从而达到快速查询的功能。

    for (int i = 1;i <= n; ++ i)
        scanf ("%d", &f[i][0]);
    for (int i = 1;i < 21; ++ i) {
        int t1 = 1 << i - 1, t2;
        t2 = t1 << 1;
        for (int j = 1;j + t2 <= n + 1; ++ j)
            f[j][i] = min(f[j][i - 1], f[i + t1][i - 1]);
    }

文中我们使用 $f_{i,j}$ 来表示从 i 开始向后 $2^j$ 个位置中的 f 值(以最小值为例)。

令 $k = log_2(r-l+1)$,则min(f[l][k], f[r - (1 << k) + 1][k])即为 $[l,r]$ 范围内的最小值。

那么接下来要讲讲局限性。

这样求值非常的方便，但是呢 $[l,l+2^k-1]$ 与 $[r - (1 << k) + 1,r]$ 会产生交集，所以用这样的 st 表存的东西必须可重复贡献，例如最大最小值，最大公约数，最小公倍数，位或，位与等等，这样便可以对两个交集不为空的区间进行合并了，还要符合结合率哦。

板题 P2880

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e4 + 5;
int minn[N][21], maxn[N][21];
int n, q;
int main() {
    scanf ("%d%d", &n, &q);
    for (int i = 1;i <= n; ++ i) {
        scanf ("%d", &minn[i][0]);
        maxn[i][0] = minn[i][0];
    }
    for (int i = 1;i < 21; ++ i) {
        int t1 = 1 << i - 1, t2;
        t2 = t1 << 1;
        for (int j = 1, k = t1 + 1;j + t2 <= n + 1; ++ j, ++ k) {
            minn[j][i] = min(minn[j][i - 1], minn[k][i - 1]);
            maxn[j][i] = max(maxn[j][i - 1], maxn[k][i - 1]);
        }
    }
    while (q --) {
        int l, r;
        scanf ("%d%d", &l, &r);
        int k = log2(r - l + 1);
        printf ("%d\n", max(maxn[l][k], maxn[r - (1 << k) + 1][k]) - min(minn[l][k], minn[r - (1 << k) + 1][k]));
    }
    
    return 0;
}

P.S. 取 log 也需要时间，所以 log 值可以预处理出来。

for (int i = 2;i <= n; ++ i)
	log[i] = log[i >> 1] + 1;