P3865 【模板】ST表 – Xhesica's blog

链接：P3865

-----------------------------------

st表是一个用来解决RMQ问题的表

st表是一个二维数组，表示的是i~i+2^j-1范围的最值

（这东西和区间DP好像）

----------------------------------

初始化：

因为2^0=1;

所以说st[i][0]存的就是i~i范围的最值（就是他自己）

    for(int i=1;i<=n;++i){
        cin>>st[i][0];
    }

初始化

建立：

我们维护的是长度为2的整数

幂长的区间

对于任何一个区间，我们考虑把他平分成两部分

例如对于st[i][j]，我们把它分成st[i][j-1]和st[i+(1<<(j-1)][j-1]两部分，即为分成一半

然后取他们的最值就行了

    for(int j=1;j<=21;j++)
        for(int i=1;i+(1<<j)-1<=n;++i)
            st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);

建立

查询：

我们查询的区间长度当然不会全是2的整数次幂

然而我们又不能查大了（越界）

就只能查小的，这样就覆盖不了整个区间，怎么办呢？

我们可以从左右端点分别查询2^k的长度，这样就可以保证覆盖掉整个区间又不越界了

    for(int i=1;i<=m;++i){
        scanf("%d%d",&l,&r);
        int k=log2(r-l+1);
        printf("%dn",max(st[l][k],st[r-(1<<k)+1][k]));
    }

查询

完整代码：

 1 #include<iostream>
 2 #include<cmath>
 3 #include<cstdio>
 4 using namespace std;
 5 int st[1000001][50];
 6 int l,r;
 7 int n,m;
 8 int main(){
 9     scanf("%d%d",&n,&m);
10     for(int i=1;i<=n;++i){
11         cin>>st[i][0];
12     }
13     for(int j=1;j<=21;j++)
14         for(int i=1;i+(1<<j)-1<=n;++i)
15             st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
16     for(int i=1;i<=m;++i){
17         scanf("%d%d",&l,&r);
18         int k=log2(r-l+1);
19         printf("%dn",max(st[l][k],st[r-(1<<k)+1][k]));
20     }
21     return 0;
22 }

发送评论 编辑评论

发送评论编辑评论