ST表 Sparse Table

ST 表是用于解决可重复贡献问题的数据结构。

可重复贡献问题是指对于运算 $\operatorname{opt}$ ，满足 $x\operatorname{opt} x=x$ ，则对应的区间询问就是一个可重复贡献问题。例如，最大值有 $\max(x,x)=x$ ，gcd 有 $\operatorname{gcd}(x,x)=x$ ，所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质，如果求区间和的时候采用的预处理区间重叠了，则会导致重叠部分被计算两次，这是我们所不愿意看到的。另外， $\operatorname{opt}$ 还必须满足结合律才能使用 ST 表求解。

模板题P3865:

给定一个长度为 $N$ 的数列，和 $M$ 次询问（查询区间 $[l_i,r_i]$ ），求出每一次询问的区间内数字的最大值。

ST表基于倍增的思想，也类似线段树，但是比倍增和线段数强的地方在于可以做到每次查询 $O(1)$ 的复杂度。

因为max操作具有可重复贡献性，所以即使查询用到的区域有重叠，给出的结果也是正确的。实际上任何区域可以用两个可能有重叠的区域来覆盖，这样对于大量查询的问题就更快。

基于ST表的解法:

预处理：令 $f(i,j)$ 为 $[i,i+2^j-1]$ 的最大值。可知 $f(i,j)$ 可以 $O(n\log n)$ 完成初始化。
查询: 对于任何 $[l,r]$ ，我们分成 $[l,l+2^s-1]$ 和 $[r-2^s+1,r]$ ，其中 $s=\left\lfloor\log_2(r-l+1)\right\rfloor$ ，即可完成查询。

查询过程如下图所示：

实现代码：

#include <bits/stdc++.h>
using namespace std;
const int logn = 21;
const int maxn = 2000001;
int f[maxn][logn + 1], Logn[maxn + 1];
 
inline int read() {  // 快读
  char c = getchar();
  int x = 0, f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * f;
}
 
void pre() {  // 准备工作，初始化
  Logn[1] = 0;
  Logn[2] = 1;
  for (int i = 3; i < maxn; i++) {
    Logn[i] = Logn[i / 2] + 1;
  }
}
 
int main() {
  int n = read(), m = read();
  for (int i = 1; i <= n; i++) f[i][0] = read();
  pre();
  for (int j = 1; j <= logn; 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]);  // ST表具体实现
  for (int i = 1; i <= m; i++) {
    int x = read(), y = read();
    int s = Logn[y - x + 1];
    printf("%d\n", max(f[x][s], f[y - (1 << s) + 1][s]));
  }
  return 0;
}

习题
P2880	USACO Gold	Balanced Lineup		普及/提高-
P2048	NOI	超级钢琴	2010	省选/NOI-		算法标签前缀和, ST