ST 表

参考资料

• ST 表 - OI Wiki

简介

ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题 的数据结构。

实现

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$ 次询问，求出每一次询问的区间内数字的最大值。