Sparse Table

ST表

定义

ST表(稀疏表)是一种基于倍增思想，用于解决可重复贡献问题的数据结构。

ST表应用最广泛的领域便是解决RMQ问题(Range Minimum/Maximum Query)：给定n个数，m个询问，对于每个询问，需要回答区间[ l , r ] 中的最大值或最小值(可以采用两个数组同时进行处理)。

基于倍增的思想，ST表可以实现O(nlogn)下进行预处理，并在O(1) 时间内回答每个询问。如果仅仅进行区间最值查询，ST表的效率完全吊打线段树；但是，相比于线段树，ST表并不支持修改操作，无论是单点修改还是区间修改都不支持。

什么是可重复贡献问题

可重复贡献问题是对于运算o p t ，运算的性质满足x o p t x = x ，则对应的区间询问就是一个可重复的贡献问题，例如：最大值满足m a x ( x , x ) = x ，最大公因数满足g c d ( x , x ) = x ，因此RMQ问题和GCD问题就是一个可重复贡献的问题，但是例如区间和就不满足这个性质，因为在求解区间和的过程中采用的预处理区间会发生重叠，导致重叠部分被重复计算，因此对于o p t 操作还需要满足集合率才能够使用ST表进行求解。

重点：求[l,r]区间的最大值或最小值是可重复贡献问题，而求和不是可重复贡献问题。

ST表的原理和实现

我们发现，区间最大值是一个具有“可重复贡献”性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。

以最大值为例，设f [ i ] [ j ] 表示整个数列A中下标在子区间[ i , i + $2{^j}$ − 1 ] 里的数的最大值，也就是从i开始的$2{^j}$ 个数的最大值。递推边界显然是f [ i ] [ 0 ] = A [ i ] ，即数列A在区间[ i , i ]里的最大值。

初始化

在递推时，我们把子区间的长度成倍增加，于是我们就能轻轻松松得到下面的这个递推表达式：

f[i][j]=max(f[i][j−1],f[i+$2^{j−1}$][j−1])

void Initial() {
    for (int i = 1; i <= n; i++)
        f[i][0] = a[i];
    int t = log(n) / log(2) + 1;
    for (int j = 1; j < t; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
            //如果求最小值这行需要改成min
        }
    }
}

查询

查询区间最大值

int query_Max(int l, int r) {
    int k = log(r - l + 1) / log(2);
    return max(f[l][k], f[r - (1 << k) + 1][k])
}

查询区间最小值

int query_Min(int l, int r) {
    int k = log(r - l + 1) / log(2);
    return min(f[l][k], f[r - (1 << k) + 1][k])
}

ST表的其他应用

除 RMQ 以外，还有其它的“可重复贡献问题”。例如“区间按位和”、“区间按位或”、“区间 GCD”，ST 表都能高效地解决。

需要注意的是，对于“区间 GCD”，ST 表的查询复杂度并没有比线段树更优（令值域为 w，ST 表的查询复杂度为 Θ ( log ⁡ w ) ，而线段树为 Θ ( log ⁡ n + log ⁡ w ) ，且值域一般是大于 n 的），但是 ST 表的预处理复杂度也没有比线段树更劣，而编程复杂度方面 ST 表比线段树简单很多。

如果分析一下，“可重复贡献问题”一般都带有某种类似 RMQ 的成分。例如“区间按位与”就是每一位取最小值，而“区间 GCD”则是每一个质因数的指数取最小值。

模板题

这是之前用树状数组AC过的模板题，主要适用于ST表，所以在这放一下别人ST表的AC代码。

Balanced Lineup G

[USACO07JAN] Balanced Lineup G

题目描述

每天,农夫 John 的 $n(1\le n\le 5\times 10^4)$ 头牛总是按同一序列排队。

有一天, John 决定让一些牛们玩一场飞盘比赛。他准备找一群在队列中位置连续的牛来进行比赛。但是为了避免水平悬殊，牛的身高不应该相差太大。John 准备了 $q(1\le q\le 1.8\times10^5)$ 个可能的牛的选择和所有牛的身高 $h_i(1\le h_i\le 10^6,1\le i\le n)$。他想知道每一组里面最高和最低的牛的身高差。

输入格式

第一行两个数 $n,q$。

接下来 $n$ 行，每行一个数 $h_i$。

再接下来 $q$ 行，每行两个整数 $a$ 和 $b$，表示询问第 $a$ 头牛到第 $b$ 头牛里的最高和最低的牛的身高差。

输出格式

输出共 $q$ 行，对于每一组询问，输出每一组中最高和最低的牛的身高差。

样例 #1

样例输入 #1

6 3
1
7
3
4
2
5
1 5
4 6
2 2

样例输出 #1

6
3
0

AC代码

改了一下码风，原来的码风太丑了。

#include <bits/stdc++.h>
using namespace std;
#define M 2000007
int maxi[M][22], mini[M][21];
int n, m;
int ST(int l, int r) {
    int s = log2(r - l + 1), x, y;
    // log2(r-l+1)是以2为底的对数，写成等式就是，2的log2(r-l+1)次方等于(r-l+1);
    x = max(maxi[l][s], maxi[r - (1 << s) + 1][s]);  // 区间最大
    y = min(mini[l][s], mini[r - (1 << s) + 1][s]);  // 区间最小
    return x - y;
}
int main() {
    scanf("%d%d", &n, &m);  // 输入
    for (int i = 1; i <= n; i++)
        scanf("%d", &maxi[i][0]), mini[i][0] = maxi[i][0];
    for (int i = 1; i <= 21; i++)
        // 这个循环的上界决定于数据的大小，即2的21次方大于数据，如果数据在大上界调高，logn是这个循环
        for (int k = 1; k + (1 << i) <= n + 1; k++) {
            // 接进于n，算成n，其实没那么大
            maxi[k][i] = max(maxi[k][i - 1], maxi[k + (1 << (i - 1))][i - 1]);
            mini[k][i] = min(mini[k][i - 1], mini[k + (1 << (i - 1))][i - 1]);
            // 神奇冻柜方程处理
        }
    int l, r;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &l, &r);
        printf("%d\n", ST(l, r));
    }
    return 0;
}