首页技术正文

RMQ求解->ST表

开发者若曦技术 2022年11月15日

0 收藏 422 点赞 4,495 浏览 1032 个字

ST表

这是一种神奇的数据结构，用nlogn的空间与nlongn的预处理得出O(1)的区间最大最小值(无修)

那么来看看这个核心数组：ST[][]

ST[i][j]表示从i到i+(1<<j)的范围内的最大/最小值

那么来看看代码吧。

 #include <cstdio>
 #include <algorithm>
 using namespace std;
 int ST[][],n;
 void makeST()
 {
     for(int j=;j<=;j++)
     {
         for(int i=;i+(<<j)-<=n;i++)  ST[i][j]=min(ST[i][j-],ST[i+(<<(j-))][j-]);
     }
     return;
 }
 int getpow(int x)
 {
    int ans=;
    while((<<ans)<=x) ans++;
    return ans-;
 }
 int main()
 {
     int m;
     scanf("%d%d",&n,&m);
     for(int i=;i<=n;i++)
     {
         scanf("%d",&ST[i][]);
     }
     makeST();
     int x,y;
     while(m--)
     {
         scanf("%d%d",&x,&y);
         int t=getpow(y-x+);
         printf("%d ",min(ST[x][t],ST[y-(<<t)+][t]));
     }
     return ;
 }

P1816 忠诚

 #include <cstdio>
 #include <algorithm>
 using namespace std;
 int ST[][],n;
 void makeST()
 {
     for(int j=;j<=;j++)
     {
         for(int i=;i+(<<j)-<=n;i++)  ST[i][j]=max(ST[i][j-],ST[i+(<<(j-))][j-]);
     }
     return;
 }
 int getpow(int x)
 {
    int ans=;
    while((<<ans)<=x) ans++;
    return ans-;
 }
 int main()
 {
     int m;
     scanf("%d%d",&n,&m);
     for(int i=;i<=n;i++)
     {
         scanf("%d",&ST[i][]);
     }
     makeST();
     int x,y;     while(m--)
     {
         scanf("%d%d",&x,&y);
         int t=getpow(y-x+);
         printf("%d\n",max(ST[x][t],ST[y-(<<t)+][t]));
     }     return ;
 }