RMQ模板

RMQ:范围最小值问题。给出一个n个元素的数组A1,A2,...,An，设计一个数据结构支持查询操作Query(L,R):计算min{AL,AL+1,...,AR}。

每次用一个循环来求最小值显然不够快快，前缀和的思想也不能提高效率，这时候ST算法就派上用场了，它预处理的时间是O(nlogn)，但是查询只需要Q（1），而且常数很小。

令dp[i][j]表示从i开始的，长度为2^j的一段元素中的最小值，递推公式：dp[i][j]=min{dp[i][j-1],dp[i+2^(j-1)][j-1]}

模板代码：

void RMQ_init(const vector<int> &A)

{

    int n=A.size();

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

        d[i][]=A[i];

        for(int j=;(<<j)<=n;++j) //长度

            for(int i=;i+(<<j)- <= n;++i) //起点，虽然书上写的是 < n

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

}

int RMQ(int L,int R)

{

    int k=;

    while((<<(k+))<=R-L+) k++; //int k=(int)((log(R-L+1))/log(2.0));

    return min(d[L][k],d[R-(<<k)+][k]);

}

模板题：南阳理工119

题意：求一段区间内的最大值和最小值之差，所以统计最大值和最小值分别用RMQ来统计

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int Max =  + ;

 int maxsum[Max][],minsum[Max][];

 int n,q,v;

 void RMQ_init()

 {

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

     {

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

         {

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

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

         }

     }

 }

 int RMQ(int l, int r)

 {

     int k = ;

     while( ( << (k + )) <= (r - l + ))

         k++;

     int maxn = max(maxsum[l][k], maxsum[r - ( << k) + ][k]);

     int minn = min(minsum[l][k], minsum[r - ( << k) + ][k]);

     return maxn - minn;

 }

 int main()

 {

     while(scanf("%d%d", &n, &q) != EOF)

     {

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

         {

             scanf("%d", &v);

             minsum[i][] = maxsum[i][] = v;

         }

         RMQ_init();

         while(q--)

         {

             int a,b;

             scanf("%d%d", &a, &b);

             printf("%d\n", RMQ(a,b));

         }

     }

     return ;

 }

巴特西

RMQ模板

最新文章

热门文章