ST表解决RMQ问题

本文主要是介绍ST表解决RMQ问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

RMQ（区间最值查询），可以用线段树和ST表解决

• 线段树 预处理 O (nlogn) 查询 O (logn) 支持在线修改

• ST表 预处理 O (nlogn) 查询O(1) 不支持在线修改

1.区间最值差—可用线段树，但ST更短

#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
const int N = 50010;
int a[N];
int n,m;
int Fmax[N][20];
int Fmin[N][20];
void init()
{
	for(int i=1;i<N;i++)Fmax[i][0]=Fmin[i][0]=a[i];
	int k=log2(n);
	for(int j=1;j<=k;j++)
		for(int i=1;i<=n-(1<<j)+1;i++)
		{
			Fmax[i][j]=max(Fmax[i][j-1],Fmax[i+(1<<j-1)][j-1]);
			Fmin[i][j]=min(Fmin[i][j-1],Fmin[i+(1<<j-1)][j-1]);
		}
			
}
int RMQ(int l,int r)
{
	int k=log2(r-l+1);
	int m1=max(Fmax[l][k],Fmax[r-(1<<k)+1][k]);
	int m2=min(Fmin[l][k],Fmin[r-(1<<k)+1][k]);
	return m1-m2;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	init();
	while(m--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",RMQ(l,r));
	}
}

2.最频繁值

#include <iostream>
#include <cmath>
#include <stdio.h>
using namespace std;
const int N = 100010;
int a[N],cnt[N]={0};
int n,m;
int f[N][20];
int lg2[N];
void init_log()
{
    lg2[0]=-1;
    for(int i=1;i<N;i++)lg2[i]=lg2[i>>1]+1;
}
void init_ST()
{
    for(int i=1;i<=n;i++)f[i][0]=cnt[i];
    for(int j=1;j<=lg2[n];j++)
        for(int i=1;i+(1<<j)-1<N;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
int RMQ(int l,int r)
{
    int k=lg2[r-l+1];
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{
    scanf("%d",&m);
    
    for(int i=1;i<=n;i++)
    {   
        scanf("%d",a+i);
        if(a[i]!=a[i-1])cnt[i]=1;
        else cnt[i]=cnt[i-1]+1;
    }
    init_ST();
    while (m -- ){
        int l,r;
        scanf("%d%d",&l,&r);
        int t=l;
        while(a[t]==a[l-1]&&t<=r)t++;
        if(t>r)printf("%d\n",t-l);
        else printf("%d\n",max(t-l,RMQ(t,r)));
    }
}
signed main()
{
    init_log();
    while(cin>>n,n)solve();
}

3.炸鸡块君与FIFA22

#include <iostream>
using namespace std;
const int N = 200010;
int f[3][N][20];
char s[N];
signed main()
{
	int n,m;
    cin>>n>>m;
    cin>> s+1 ;
    for(int j=0;j<3;j++)
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='W')f[j][i][0]=1;
            else if(s[i]=='L')
            {
                if(!j)f[j][i][0]=0;
                else f[j][i][0]=-1;
            }
            else f[j][i][0]=0;
        }
    //类似于区间DP   初始化ST表
    for(int j=1;j<=20;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            for(int k=0;k<3;k++)
                f[k][i][j]=f[k][i][j-1]+f[(k+f[k][i][j-1])%3][i+(1<<j-1)][j-1];
    // query ST
    int l,r,x;
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&x);
        for(int j=20;j>=0;j--)
        {
            if(l+(1<<j)-1>r)continue;
            x+=f[x%3][l][j];
            l+=(1<<j);
        }
        printf("%d\n",x);
    }
}

这篇关于ST表解决RMQ问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！