【学习笔记】静态区间最大值

题意简述

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

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

ST表做法

//ST表
#include <bits/stdc++.h>
using namespace std;
int lg[100010],f[100010][30],n,m;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main()
{
	n=read(),m=read();
	lg[1]=0;
	for(int i=2;i<=n;i++)lg[i]=lg[i/2]+1;
	for(int i=1;i<=n;i++)
		f[i][0]=read();
	for(int j=1;j<=lg[n];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++)
	{
		int l=read(),r=read(),k=lg[r-l+1];
		printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));
	}
	return 0;
}

线段树做法

// Problem:P3865 【模板】ST 表 & RMQ 问题
// Contest:Luogu
// URL:https://www.luogu.com.cn/problem/P3865
// Memory Limit:125 MB
// Time Limit:800 ms

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int n,m,a[MAXN+10],val[(MAXN<<2)+10];
int ls(int i){return i<<1;}
int rs(int i){return i<<1|1;}
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0',c=getchar();}
	return x*f;
}
void pushup(int pos)
{
	val[pos]=max(val[ls(pos)],val[rs(pos)]);
}
void build(int pos,int l,int r)
{
	if(l==r){val[pos]=a[l];return ;}
	int mid=l+((r-l)>>1);
	build(ls(pos),l,mid),build(rs(pos),mid+1,r);
	pushup(pos);
}
int query(int pos,int ql,int qr,int l,int r)
{
	if(qr<l||ql>r)return INT_MIN;
	if(ql<=l&&r<=qr)return val[pos];
	int mid=l+((r-l)>>1);
	//pushdown()
	return max(query(ls(pos),ql,qr,l,mid),query(rs(pos),ql,qr,mid+1,r));
}
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	build(1,1,n);
	while(m--)
	{
		int l=read(),r=read();
		cout<<query(1,l,r,1,n)<<'\n';
	}
	return 0;
}

树状数组做法

// Problem:P3865 【模板】ST 表 & RMQ 问题
// Contest:Luogu
// URL:https://www.luogu.com.cn/problem/P3865
// Memory Limit:125 MB
// Time Limit:800 ms

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e5+10;
int a[MAXN],n,m;
int lowbit(int i){return i & -i;}
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c))x=x*10+c-'0',c=getchar();
	return x*f;
}
struct fenwick
{
	int t[MAXN];
	void build()
	{
		for(int i=1;i<=n;i++)
		{
			t[i]=max(t[i],a[i]);
			if(i+lowbit(i)<=n)t[i+lowbit(i)]=max(t[i+lowbit(i)],t[i]);
		}
	}
	int query(int l,int r)
	{
		int ret=0;
		while(r>=l)
			if(r-lowbit(r)>=l)ret=max(ret,t[r]),r-=lowbit(r);
			else ret=max(ret,a[r]),r--;
		return ret;
	}
}t;
signed main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	t.build();
	while(m--)
	{
		int l=read(),r=read();
		cout<<t.query(l,r)<<'\n';
	}
	return 0;
}