代码模板-ST 表

ST 表基于倍增思想，用 $st[i][j]$ 维护以 $i$ 为左端点、长度为 $2^j$ 的区间 $[i,\,i+2^j-1]$ 的最值，由两个长度为 $2^{j-1}$ 的子区间合并而来。预处理 $O(n\log n)$ ，单次查询 $O(1)$ ，但不支持修改，适用于离线 RMQ 问题。

区间最值查询（维护最大值）

const int N = 1e5 + 5, M = 17;   // M = floor(log2(N)) + 1
int a[N], st[N][M], lg[N];

void ST_init(int n) {                       // 预处理
    lg[1] = 0;
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;  // 预处理 log2，避免查询时调用对数函数
    for (int i = 1; i <= n; i++) st[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}

int ST_query(int l, int r) {                // 查询 [l, r] 的最大值
    int k = lg[r - l + 1];
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

查询时用两个长度为 $2^k$ 的区间覆盖 $[l,r]$ ，其中 $k$ 是满足 $2^k \le r-l+1$ 的最大整数。两区间有重叠，但因为 $\max$ 满足可重复贡献性（ $f(x,x)=x$ ），重叠部分不影响结果。

运算替换

将 max 替换为其他满足可重复贡献性的运算即可（即 $f(x,x)=x$ ，重叠区间不改变结果）：

运算	替换	说明
最大值	`max`	默认
最小值	`min`	把 `max` 全局替换
GCD	`gcd`	满足幂等性
按位与	`&`	$x\ \&\ x = x$
按位或	`\|`	$x\ \| x = x$

加法、乘法等不满足可重复贡献性的运算不能用 ST 表，需改用前缀和或线段树。

相关笔记：【数据结构】ST 表学习笔记