ST算法-RMQ专题

ST算法(解决RMQ问题)

ST算法说明及理解ST

  • RMQ问题:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在i,j之间的最小/大值
  • ST算法复杂度:利用dp思想,在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询
  • dp方程:dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
  • dp[i][j]: [i, i+(1<<j)-1]区间的最大值
  • 方程怎么来的?
    • [i, i+(2^j)-1]区间有2^j个数,而2^j = 2^(j-1) + 2^(j-1)
    • dp[i][j-1] 表示[i, i+2^(j-1)-1]区间最大值
    • dp[i+(2^(j-1))][j-1]表示区间[i+(2^(j-1)), i+(2^(j-1))+(2^(j-1))-1] = [i+(2^(j-1)), i+(2^j)-1]
    • 可知dp[i][j]的区间由dp[i][j-1]的区间和dp[i+(2^(j-1))][j-1]的区间构成,即dp[i][j] = dp[i][j-1] + dp[i+(2^(j-1))][j-1]

代码编写:

  • 变量定义

    1
    2
    3
    4
    const int maxn = 1e3; 
    int dp[maxn][30];
    int a[maxn]; //原序列
    int n;//序列长度
  • O(nlogn) 预处理

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    //dp[i][j]
    void st(){
    int i, j;
    for(i=1; i<=n; ++i) dp[i][0] = a[i];
    for(j = 1; (1<<j) <= n ; ++j){ //枚举区间长度 1<<j
    for(i=1; i+(1<<j)-1<=n; i++){ // 更新当前区间长度下的各起点所表示的区间的最大值
    dp[i][j] = max(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);// max可改成min
    }
    }
    return;
    }
    //应用:st();
  • O(1) 查询[x, y]最大值

    1
    2
    3
    4
    5
    6
    7
    8
    int query(int x, int y){
    //计算区间长度对应的log2值, 如区间长度为4那么2^2=4所以j = 2;
    int j = (int)(log(y-x+1.0)/(log(2.0)));

    // [x, x+2^j-1]和[y-2^j+1, y] 覆盖[x,y]整个区间
    return max(dp[x][j], dp[y-(1<<j)+1][j]);
    }
    //应用:query(x, y)