ST表简单笔记

萌新一枚，借鉴了许多大佬而总结下的笔记，可能有瑕疵或者错误，望指正。

1用于解决区间查询可重复贡献的问题，比如求[l,r]区间的最大值或最小值，而求和不是可重复贡献问题。

2利用倍增思想，如果只是查询，速度应该是比线段树快

3一维st表一般用一个二维数组表示，第一个下标表示区间的左端点i，第二个下标j表示i+2^j-1

,即右端点。

代码实现：

1数据存储

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int st[maxn][22];//st表
int a[maxn];//数据
int n;
int lg2[maxn];//用来记录log2(x)的值（向下取整）

2预处理st表

void init()
{
	for(int i=1;i<=n;i++)
	st[i][0]=a[i];//i+2^0-1=i.也就是单个[i,i]的区间
	for(int j=1;(1<<j)<=n;j++)//2^j不能超过n的大小
	for(int i=1;i+(1<<j)-1<=n;i++)//i+2^j-1不超过n
	st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);//由两个预处理区间[i,i+2^(j-1)-1]和
//[i+2^(j-1),j]形成[i,j]
	lg2[0]=-1;
	for(int i=1;i<=n;i++)//处理log2(i)的值
	lg2[i]=lg2[i/2]+1;
}

3区间查询

int query(int l,int r)
{
	int k=lg2[r-l+1];
	return max(st[l][k],st[r-(1<<k)+1][k]);
    由两个预处理区间[l,l+2^(k-1)-1]和[l+2^(k-1),r]重叠形成[l,r]。
}

4主函数应用

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)//n个数据
	cin>>a[i];
	init();
	int q;
	cin>>q;//q次询问
	while(q--)
	{
		int l,r;
		cin>>l>>r;
		cout<<query(l,r)<<'\n';
	} 
	return 0;
}