Sparse Table（ST 表）学习笔记

很少写算法和数据结构的讲解，但是 ST 表还是有必要写一下的，这里面细节很多。

稀疏表（ST 表）是一种常用的 RMQ 数据结构，适合于不带修改的可重复贡献问题

所谓可重复贡献问题，是指对于运算 $\operatorname{opt}$ 有 $x \operatorname{opt} x = x$ 的区间询问，例如 $\max,\min,\gcd$ 等

ST 表基于倍增的思想，可以做到 $\mathcal{O}(n \log n)$ 预处理，$\mathcal{O}(1)$ 回答询问。注意，不支持修改。

定义 $f(i,j)$ 为区间 $[i,i + 2^j -1]$ 的最大值，显然 $f(i,0) = a_i$ 。考虑转移 $j > 0$ 的情况

$f(i,j) = \max\left\{f(i,j-1),~f(i + 2^j, j - 1)\right\}$

对于询问 $[l,r]$ ，我们记 $k = \left\lfloor \log_2 (r - l + 1)\right\rfloor$ ，则询问的答案为

$\max\{f(l,k),~f(r - 2^k + 1, k)\}$

模板题代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n,Q,lg[N],st[18][N]; // 实现的时候把 i,j 交换一下位置，可以加快速度
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) cin >> st[0][i];
    for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1; // 预处理 log
    for(int j = 0; 1 << (j + 1) <= n; j++)
    {
        int *f = st[j], *g = st[j + 1];
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            g[i] = max(f[i], f[i + (1 << j)]);
    }
    for(int l,r; Q--; )
    {
        cin >> l >> r; int k = lg[r - l + 1]; // 这里写 r - l 也是可以的
        cout << max(st[k][l], st[k][r - (1 << k) + 1]) << '\n';
    }
    return 0;
}

接下来我来解释一些细节。首先预处理 log 几乎是必须的，并且一些题会卡这个（被卡过）。

可能你们会想到自带的 log() 和 log2() 函数，查阅官方文档可以发现，这些函数都是针对于浮点数的。

据我所知，这几个函数实现的时候用的应该是牛顿迭代法，复杂度会带上一个近似于 $\mathcal{O}(\log x)$ 的。

因此一般采用预处理 log ，或者用 __lg() 。后者的实现方式是利用 __builtin_clz() ，不推荐使用。

然后是询问中的 max(st[k][l], st[k][r - (1 << k) + 1]) ，可能和一些人的写法不一样。

你们有可能见过回答 max(st[l+(1<<k)-1][k], st[r][k]) 的，~~比如我以前的代码就是这么写的~~

其实它这种代码的定义跟我的不太一样，它的 $f(i,j)$ 定义的是 $[i - 2^j +1, ~i]$ 的最大值。

我以前的代码（部分），并且采用了另一种构建方式，仅供参考：

int n,m,lg[N],f[N][21];
void change(int u,int x)
{
	f[u][0]=x;
	for(int i=1; u>=(1<<i); i++)
		f[u][i]=max(f[u][i-1],f[u-(1<<(i-1))][i-1]);
}
int query(int l,int r)
{
	int k=lg[r-l+1];
	return max(f[l+(1<<k)-1][k],f[r][k]);
}
signed main()
{
	read(n);read(m);
	for(int i=1,x; i<=n; i++)
	{
		read(x); change(i,x);
        lg[i]=(double)log(i)/log(2); // 什么啥b预处理啊。
	}
	for(int i=1,l,r; i<=m; i++)
	{
		read(l);read(r);
		write(query(l,r));pc('\n');
	}
	return 0;
}