ST表

ST表（Sparse Table，稀疏表）是一种简单的数据结构，主要用来解决静态RMQ（区间最值查询）问题。
它应用倍增的思想，只要花费$O(n\log n)$的预处理，就能在 $O(1)$ 内求出原序列某段子区间的最值。

所谓静态，就是数组内部的值始终不发生修改

对于一个长度为$N$的序列$a$，其子区间个数显然有$N^2$个，那么根据倍增思想，我们首先在这$O(N^2)$的状态空间，选取2的整数次幂的位置作为代表值。具体来说，我们可以使用动态规划的思想，预处理出一个二维数组 $f[i][j]$， $f[i][j]$ 表示从 $i$ 开始、长度为 $2^j$ 的区间中的最值，即：

$mx[i][j] = \max{ \left \{ a_{i},a_{i+1},\ldots,a_{i+2^{j}-1} \right \} }$

$mn[i][j] = \min{ \left \{ a_{i},a_{i+1},\ldots,a_{i+2^{j}-1} \right \} }$

可以看出，$f[i][j]$ 的第一维是下标，第二维是区间长度所对应的二进制位数，因此该数组的空间大小 $O(n\log n)$。

构建(build)

ST表是基于倍增思想的。

我们设$f[i][j]$表示区间 $[i, i + 2 ^ j - 1]$ 内的最值，显然有初始状态 $f[i][0] = max[i, i] = a[i]$。

由倍增思想可得，跳$2^i$步相当于先跳$2^{i - 1}$步再跳$2^{i - 1}$步；同理，区间$[i, i + 2 ^ j - 1]$的最值，可以通过取它的两个子区间$[i, i + 2 ^ {j - 1} - 1]$和$[i + 2 ^ {j - 1}, i + 2 ^ j -1]$的最值得到。

所以可得状态转移方程：

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

因此只需要先枚举区间长度(也就是枚举j)，再枚举起点(也就是枚举i)，就能使得ST表由区间长度从小到大递推构建。

查询(query)

建立好 $f[i][j]$ 数组之后，要查询区间 $[l,r]$ 的最值，我们当然希望直接输出$f[l][k]$，即$l + 2 ^ k - 1 = r$

由上式可得：

$k = log_2(r - l + 1)$

但是经过对数运算后，求得的$k$不一定是整数，因此很可能无法正好覆盖区间$[l, r]$。

举个例子：对于求区间[1, 9]的最值，$k = log_2(9)$不是整数，$k$要是强行取整无法正好覆盖[l, r]

所以这里有一个方法，就是把区间$[l, r]$分为两个子区间$[l, l + 2 ^ k - 1]$和$[r - 2 ^ k + 1, r]$，让这左右两个重叠的相同长度子区间完成区间覆盖，再求最值

Step1：计算 $k=\lfloor\log_2(r - l + 1)\rfloor$，即对$k$向下取整，找到最接近且不大于[查询区间长度]的区间长度
Step2：取$\max{(f[l][k],f[r-2^{k}+1][k])}$，以为$k$为区间长度所对应的二进制数，求这两个子区间的最值

举个例子：对于求区间[1, 9]的最值，k向下取整得3，因此子区间是[1, 8]和[2, 9]

不难发现，虽然两个区间会有部分重叠，但对于求最值不会影响最终结果。

每次计算$\log2$太花时间了，我们可以在build中对$\log2$的计算也进行一次递推的预处理：

lg[0] = -1;
for (int i = 1; i <= n; i++)  lg[i] = lg[i >> 1] + 1; // 已向下取整

---

1-basedST表板子如下：

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 7;

struct SparseTable {
	int lg[N], mx[N][21], mn[N][21];
	void build(vector<int>& a, int n) {
		lg[0] = -1;
		for(int i = 1; i <= n; i++) lg[i] = lg[i >> 1] + 1;
		for(int i = 1; i <= n; i++) mx[i][0] = mn[i][0] = a[i];
		for(int j = 1; 1 << j <= n; j++) for(int i = 1; i + (1 << j) - 1 <= n; i++) {
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
            mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
        }
	}
	int qmax(int l, int r) {
		int k = lg[r - l + 1];
		return max(mx[l][k], mx[r - (1 << k) + 1][k]);
	}
	int qmin(int l, int r) {
		int k = lg[r - l + 1];
		return min(mn[l][k], mn[r - (1 << k) + 1][k]);
	}
};

int main() {
	int n, m;
    cin >> n >> m;
    vector<int>a(n + 1); // 1-based, n个数组成数组
    for (int i = 1 ; i <= n; i++) {
		cin >> a[i];
    }
    
    SparseTable st;
    st.build(a, n); // 构建st表
    // m次在线查询
    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("max:%d min:%d\n", st.qmax(l, r), st.qmin(l, r));
    }
    return 0;
}

使用时要注意：

• 这个板子中的SparseTable和build时使用的vector<int> a都是1-based的

• 关于mx[N][21]和mn[N][21]的第二维，不一定要是21，只要求$\ge \log_2(N)$即可。因为复杂度的关系N一般取1e5，因此第二维最小其实可以是18

• 求k时的log计算，也可以使用头文件<cmath>自带的

  #include <cmath>
  
  int qmax(int l, int r) {
      double t = log(r - l + 1) / log(2);
      int k = t; // 向下取整
      return max(mx[l][k], mx[r - (1 << k) + 1][k]);
  }

复杂度分析

• 时间复杂度：
  • 构建：$O(n \log n )$，时间主要花费在在构建ST表预处理中的双重循环
  • 查询：$O(1)$
• 空间复杂度：$O(n \log n)$，空间主要花费在mx[N][21]和mn[N][21]上

拓展

可重复贡献问题

常见的可重复贡献问题有：区间最值、区间按位与、区间按位或、区间GCD等。

• 区间按位与，只需修改以下代码：

  f[i][j]=f[i][j-1]&f[i+(1<<(j-1))][j-1];       // 倍增的预处理
  ans=f[l][lg]&f[r-(1<<lg)+1][lg];              // 区间重叠运算

• 区间GCD，只需修改成以下代码：

  f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);  // 倍增的预处理
  ans=gcd(f[l][lg],f[r-(1<<lg)+1][lg]);         // 区间重叠运算

  值得一提的是，处理区间GCD时，ST表与线段树的时间复杂度基本相近，但前者却显然要好写得多。

练习eg:

P3865.【模板】ST 表

leetcode-6911.不间断子数组

P2471 [SCOI2007]. 降雨量