【暑假】[实用数据结构]范围最小值问题（RMQ）

范围最小值问题：

提供操作：

Query(L,R)：计算min{A_L~ A_R}

Sparse-Table算法：

定义d[i][j]为从i开始长度为2^j的一段元素的最小值。所以可以用递推的方法表示。

预处理RMQ_init如下（感觉像区间DP）：

 int 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++)

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

 }

询问回值RMQ如下：

int RMQ(int L,int R){

    int k=;

    while((<<(k+))<=R-L+) k++;

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

    //左右结点均覆盖确保不遗漏

}

作者所给模板：

 struct RMQ {

   int d[maxn][maxlog];

   void 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++)

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

   }

   int query(int L, int R) {

     int k = ;

     while((<<(k+)) <= R-L+) k++; // 如果2^(k+1)<=R-L+1，那么k还可以加1

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

   }

 };

练习题目：UVa 11235

链接：

巴特西

【暑假】[实用数据结构]范围最小值问题（RMQ）

最新文章

热门文章