ST表学习笔记

发布于 2019-07-24  533 次阅读


其实就是复制过来做笔记嘤

ST表

ST表的功能很简单

它是解决RMQ问题(区间最值问题)的一种强有力的工具

它可以做到O(nlogn)预处理,O(1)查询最值

算法

ST表是利用的是倍增的思想

拿最大值来说

img img

来一道例题

代码如下:

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

int n,m,x,f[100010][233],l,r,p,t;

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		f[i][0]=x;
	}
	t=log(n)/log(2);//利用换底公式改成以2为底
	for(int j=1;j<=t;j++)
		for (int i=1;i<=n-(1<<j)+1;i++)
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&l,&r);
		p=log(r-l+1)/log(2);
		printf("%d",max(f[l][p],f[r-(1<<p)+1][p]));
	}
	return 0;
}


最美好的事情就是和OI一起成长呢。