ST 表

ST 表也可以看做是一种区间 DP。

不过它有自己的独特之处，所以和其他区间 DP 显得很不一样。

ST 表是一种用倍增法解决可重复贡献问题的（离线）（区间查询）算法，可以做到 $O(n \log_2n)$ 预处理， $O(1)$ 回答。

和树状数组、线段树等不同，ST 表查询很快，可以处理 1e9 级别的数据。也就是说，1e9 级别基本就是 ST 表了，线段树就别想了。

什么是“可重复贡献问题”？

定义 “ $\circ$ ” 为一种二元运算，如果这种运算满足 $x \circ x=x$ ，就说求区间上若干个 $x_i$ 连 $\circ$ 是一个可重复贡献问题。

实例：区间最大/最小值（Range Maximun/Minnimun Query, RMQ）、GCD 等。（如 $\max\{x,x\}=x$ ）

反例：区间和、区间积等。（如 $x+x\not=x$ ）

正题

为了叙述方便，下面都以维护区间最大值为例讲解，其他的操作类似。

定义 $\text{ST}[i][j]$ 表示区间 $[i,i+2^j-1]$ 上的最大值。即左端点为 $i$ ，包含 $2^j$ 个数的区间。一般代码里面是这样开数组的：

const int MAXN = 1000;
int st[MAXN][10]; // 2^10 = 1024 > 1000

一般来说，应用 ST 表有两步：

预处理 ST 表，时间复杂度 $O(n\log_2n)$ 。
离线处理区间查询（直接查表），时间复杂度 $O(1)$ 。

预处理

通过递推来预处理。根据定义，容易得到递推式：

\text{ST}[i][j]=\max\{\text{ST}[i][j-1],\text{ST}[i+2^j-1][j-1]\}

分析：

$\text{ST}[i][j-1]\longrightarrow区间[i,i+2^{j-1}-1]$ 。
$\text{ST}[i+2^{j-1}][j-1]\longrightarrow区间[i+2^j-1,(i+2^{j-1})+2^{j-1}-1]\space即\space区间[i+2^j-1,i+2^j-1]$ 。
两个区间取并集，就是 $\text{ST}[i][j]\longrightarrow区间[i,i+2^j-1]$ 。

这样，我们就可以由 $\text{ST}[...][j-1]$ 递推到 $\text{ST}[...][j]$ 。

for (int i = 1; i <= n; i++) cin >> st[i][0]; // 直接输入到 st[i][0]，省事
// 预处理
for (int j = 1; (1<<j) <= n; j++) {
    // (1<<j) <= n 防止越界
    // 外层是 j 循环
    for (int i = 1; i+(1<<j)-1 <= n; i++) {
        // 这里也要 i+(1<<j)-1 <= n 防止越界
        st[i][j] = max(st[i][j-1], st[i+(1<<j-1)][j-1]); // 1<<j-1 就是 1<<(j-1)
    }
}

查表

设我们要查询 $[L,R]$ 上的区间最大值。

我们想要把 $[L,R]$ 分为两个长度相等、首尾相连的小区间，然后通过求这两个小区间的最大值求得 $[L,R]$ 的最大值。

假设两个小区间的长度都为 $x$ ，区间 $[L,R]$ 的长度 $\text{len}=R-L+1$ 。令 $x$ 为小于 $\text{len}$ 的 $2$ 的最高次幂，则有 $x\leq\text{len}\leq2x$ ，可以保证一定覆盖 $[L,R]$ 。（可能会在中间重合）

所以我们想要的两个区间是： $[L,L+x-1]$ 、 $[R-x+1,R]$ 。两个区间的长度都是 $x$ 。

即： $\text{ST}[L][\log_2x]$ 、 $\text{ST}[R-x+1][\log_2x]$ 。

实际编码时，我们先求出 $k=\lfloor\log_2\text{len}\rfloor$ ，于是有 $2^k=x$ 。我们用 $k$ 来计算，而不是 $x$ 。

cin >> L >> R;
int k = Log2[R-L+1];
cout << max(st[L][k], st[R-(1<<k)+1][k] << endl;

因为每次查询都要调用 log() 太慢了，我们选择自己预处理 Log2[]：

// 预处理 Log2[]
Log2[1] = 0;
for (int i = 2; i <= n; i++) {
    Log2[i] = Log2[i>>1] + 1;
}

什么是“可重复贡献问题”？​

正题​

预处理​

查表​

什么是“可重复贡献问题”？

正题

预处理

查表