数据结构：ST表

BZOJ1699

在经历了树套树和主席树的洗礼之后，所有的数据结构都显得格外地亲切，和自然。。

ST算法能够实现O（nlogn）的预处理的情况下完成O（1）的区间最值查询

虽然这要求区间是静态的，也就是我们不能对区间进行修改

如果是动态的，区间最值问题，线段树或者分块儿

另外RMQ问题和LCA可以相互转化，我们回头单独介绍

这里先给出预处理：

（如果使用标准RMQ算法，可以完成O（n）的预处理，还有约束RMQ一类的问题）

void pre()

{

    for(int i=;i<=n;i++)

        mx[i][]=mn[i][]=a[i];

    int t=log(n)/log();

    for(int i=;i<=t;i++)

    for(int j=n;j>;j--)

    {

        mx[j][i]=mx[j][i-];

        if(j+(<<(i-))<=n)

            mx[j][i]=max(mx[j][i],mx[j+(<<(i-))][i-]);

    }

    for(int i=;i<=t;i++)

    for(int j=n;j>;j--)

    {

        mn[j][i]=mn[j][i-];

        if(j+(<<(i-))<=n)

            mn[j][i]=min(mn[j][i],mn[j+(<<(i-))][i-]);

    }

}

其实预处理就是一个递推式

然后是查询：

int rmq(int l,int r)

{

    int m=log(r-l+)/log();

    int a=max(mx[l][m],mx[r-(<<m)+][m]);

    int b=min(mn[l][m],mn[r-(<<m)+][m]);

    return a-b;

}

最后给出完整的，实现。。。

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 int n,q;

 int a[maxn],mn[maxn][],mx[maxn][];

 void pre()

 {

     for(int i=;i<=n;i++)

         mx[i][]=mn[i][]=a[i];

     int t=log(n)/log();

     for(int i=;i<=t;i++)

     for(int j=n;j>;j--)

     {

         mx[j][i]=mx[j][i-];

         if(j+(<<(i-))<=n)

             mx[j][i]=max(mx[j][i],mx[j+(<<(i-))][i-]);

     }

     for(int i=;i<=t;i++)

     for(int j=n;j>;j--)

     {

         mn[j][i]=mn[j][i-];

         if(j+(<<(i-))<=n)

             mn[j][i]=min(mn[j][i],mn[j+(<<(i-))][i-]);

     }

 }

 int rmq(int l,int r)

 {

     int m=log(r-l+)/log();

     int a=max(mx[l][m],mx[r-(<<m)+][m]);

     int b=min(mn[l][m],mn[r-(<<m)+][m]);

     return a-b;

 }

 int main()

 {

     scanf("%d%d",&n,&q);

     for(int i=;i<=n;i++)

         scanf("%d",&a[i]);

     pre();

     int x,y;

     while(q--)

     {

         scanf("%d%d",&x,&y);

         printf("%d\n",rmq(x,y));

     }

     return ;

 }

像这种成型的算法，实在理解不了就背下来，不过要先会推导否则死翘翘，硬背是会凉的。

巴特西

数据结构：ST表

最新文章

热门文章