ST表-白红宇

ST表

阅读量：5346 次

发布时间：2019-06-15

本文共 1476 字，大约阅读时间需要 4 分钟。

近期我计划要补更好多noip知识点

就先从ST表开始吧

ST表是一种编程复杂度低的用于求解RMQ问题的算法

算法核心思想运用了动态规划和倍增

以求区间最大值为例

设a[i][j]表示左端点为i ，右端点为i + (2 ^ j) - 1的区间的最大值

显然这段区间的长度为2 ^ j;

然后将这段区间分为两段长度均为2 ^ (j - 1)的子区间

一段为a[i][j - 1]，另一端为a[i + 2 ^ (j - 1)][j - 1]

所以原区间的最大值就是两个子区间最大值的较大的值

至此可以写出dp的动态转移方程:

当j == 0时 a[i][0] = 输入的序列中的第i个(即r[i]);

当j > 0时 a[i][j] = max(a[i][j - 1], a[i + 2 ^ (j - 1)][j - 1]);

至于数组a的大小要特殊说明一下

第一维的大小为输入序列的最大长度len

第二维的大小为log₂len(一般开到25 ~ 30均可)

接下来上一道例题：

下面是我的代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;const int maxn = 1e6 + 5;int a[maxn][25], n, m;int read(){ int ans = 0, op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op;}void ST(){ for(int i = 1;i <= n;i++) a[i][0] = read(); for(int j = 1;j <= 19;j++) { for(int i = 1;i + (1 << j) - 1 <= n;i++) a[i][j] = max(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]); }}int query(int l, int r){ int k = log2(r + 1 - l); return max(a[l][k], a[r - (1 << k) + 1][k]);//如需求区间最大值则将max改为min }int main(){ int n = read(), m = read(); ST(); while(m--) { int L, R; L = read(), R = read(); printf("%d\n", query(L, R)); } return 0;}