st表

st表

1简洁

st表可以\(nlogn\)预处理，O1查询，相对于线段树的logn查询相对有优势，但是st表只能支持静态解决RMQ，这是一个非常大的劣势。

2.讲解

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

拿最大值来说

我们用??????[??][??]Max[i][j]表示，从??i位置开始的2??2j个数中的最大值，例如??????[??][1]Max[i][1]表示的是??i位置和??+1i+1位置中两个数的最大值

那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值（注意这里的编号是从11开始的）

查询的时候也比较简单

我们计算出??????2(区间长度)log2(区间长度)

然后对于左端点和右端点分别进行查询，这样可以保证一定可以覆盖查询的区间

刚开始学的时候我不太理解为什么从右端点开始查的时候左端点是???2??+1r?2k+1

实际很简单，因为我们需要找到一个点??x，使得??+2???1=??x+2k?1=r

这样的话就可以得到??=???2??+1

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<deque>
#include<cstdlib>
#include<ctime>
#define dd double
#define ll long long
#define ld long double
#define ull unsigned long long
#define N 100010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

int n,m,a[N];
int sum[N][50];

inline int Min(int a,int b){
	return a>b?b:a;
}

inline int Max(int a,int b){
	return a>b?a:b;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
//	memset(sum,INF,sizeof(sum));
	for(int i=1;i<=n;i++) sum[i][0]=a[i];
	for(int i=1;(1<<i)<=n;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
			sum[j][i]=Max(sum[j][i-1],sum[j+(1<<(i-1))][i-1]);
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		int k=log2(r-l+1);
		int minn=Max(sum[l][k],sum[r-(1<<k)+1][k]);
		printf("%d\n",minn);
	}
}

引用注明

<https://www.cnblogs.com/zwfymqz/p/8581995.html

st表

原文：https://www.cnblogs.com/TianMeng-hyl/p/14393663.html