ST 表

Summary

ST 表又称稀疏表，是用于解决可重复贡献问题的数据结构。它预处理出每个以 2 的幂为长度的区间的聚合值，如区间最值；查询时用两个可重叠的等长区间覆盖待查区间，做到 O(nlogn) 预处理、O(1) 查询，适合大量查询而无修改的场景。它仅适用于满足结合律且可重复贡献的运算，如最大值、最大公约数，对求和这类重叠会重复计算的运算并不适用。给出维护区间最大值的结构体实现，含预处理与查询两个方法。附 P3865 作为模板例题。

参考资料

• ST 表 - OI Wiki

简介

ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题 的数据结构。它预处理出每个以 $2^k$ 为长度的区间的聚合值（如区间最值），查询 $[l,r]$ 时用两个可重叠的 $2^k$ 长区间覆盖，做到 $O(n\log n)$ 预处理、$O(1)$ 查询。它仅适用于满足结合律且可重复贡献的运算，如 $\max$、$\gcd$。

实现

275 Bcpp

struct ST
{
	int a[30][N];
	void init(int n)
	{
		for(int i=1;i<=__lg(n);i++)
		{
			for(int j=1;j<=n-(1<<i)+1;j++)
			{
				a[i][j]=max(a[i-1][j],a[i-1][j+(1<<(i-1))]);
			}
		}
	}
	int query(int l,int r)
	{
		int k=__lg(r-l+1);
		return max(a[k][l],a[k][r-(1<<k)+1]);
	}
};

例题

洛谷 P3865 【模板】ST 表 && RMQ 问题

给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。