ST算法------是用来求解给定区间RMQ的最值，本文以最小值为例

ST算法分为两部分

离线预处理（nlogn）：运用DP思想，用于求解区间最值，并保存到一个二维数组中。
在线查询 (O(1)）：对给定区间进行分割，借助该二维数组求最值

离线预处理

该二维数组是什么？

设该二维数组为dp[n][n]，则dp[i][j]表示以i为起点，以2^j为区间长度的区间最值即表示数组[i, i+2^j-1]区间的最值。
给出一数组A[0~5] = {5,4,6,10,1,12},则区间[2,5]之间的最值为1。
比如，dp[0][2]表示区间[0,3]的最小值，即等于4，dp[2][2]表示区间[2,5]的最小值，即等于1。

如何求一个dp[i][j]的最值?

在求解dp[i][j]时，将它表示的数组区间分成两部分即将[i,i+2^j-1]分成两份，每份区间长度为2^(j-1)。之后在分别求解这两个区间dp[i][j-1]和dp[i+2^(j-1)][j-1]的最值，然后结合这两个区间求整个区间的最值。(特殊情况：当j=0时，区间长度为1，此时区间中只有一个元素，此时dp[i][0]等于每一个元素的值)。
举例：要求解dp[1][2]的最小值，即求解区间[1, 4]={4,6,10,1}的最小值,将区间分为等长两部分[1,2],[3,4]，求这两个区间的最小值，此时这两个区间最小值又对应着dp[1][1],dp[3][1]的最小值。
状态转移方程是 dp[i][j] = min(dp[i][j - 1],dp[i + 2^(j - 1)][j - 1])
初始状态为：dp[i][0] = A[i]。
在根据状态转移方程递推时，是对每一元素，先求区间长度为1的区间最值，之后再求区间长度为2的区间最值，之后再求区间长度为4的区间最值....，最后，对每一个元素，在求解区间长度为log2^n的区间最值后，算法结束，其中n表示元素个数。即：先求dp[0][1]，dp[1][1]，dp[2][1]，dp[3][1]，,，dp[n][1]，再求.dp[0][2]，dp[1][2]，dp[2][2]，dp[3][2]，,，dp[m][2]，... 。

在线查询

这里我们是已知待查询的区间[x,y]，求解其最值。
在预处理期间，每一个状态对应的区间长度都为2^i。由于给出的待查询区间长度不一定恰好为2^i，因此我们应对待查询的区间进行处理。

这里我们把待查询的区间分成两个小区间，这两个小区间满足两个条件

这两个小区间要能覆盖整个区间
为了利用预处理的结果，要求小区间长度相等且都为2^i。注意两个小区间可能重叠。

如：待查询的区间为[3,11]，先尽量等分两个区间，则先设置为[3,7]和[8,11]。之后再扩大这两个区间，让其长度都等于为2^i。刚划分的两个区间长度分别为5和4，之后继续增加区间长度，直到其成为2^i。此时满足两个条件的最小区间长度为8,
此时i = 3在程序计算求解区间长度时，并没有那么麻烦，我们可以直接得到i，即等于直接对区间长度取以2为底的对数。这里，对于区间[3,11]，其分解的区间长度为int（log(11 - 3 + 1)） = 3，这里log是以2为底的。

然后就可以将区间 [x, y]划分成两个小区间[x,x+2^i-1],[y-2^i+1,y]即对应着dp[x][i],dp[y-2^i+1][i]

最后上代码！

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=1e5+;

int dpmin[maxn][],dpmax[maxn][];

int a[maxn];

void initrmq(int n)

{

    int i, j;

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

    {

        dpmin[i][]=a[i];

        dpmax[i][]=a[i];

    }

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

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

        {

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

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

        }

}

int queryrmq(int l, int r, int op) // 传入op=0,表示最小值，op=1，表示最大值

{

    int k=log2(r-l+);

    if(op==)

        return min(dpmin[l][k], dpmin[r-(<<k)+][k]);

    else

        return max(dpmax[l][k], dpmax[r-(<<k)+][k]);

}

int main()

{

    int i, m, q, n;

    cin>>n>>q;

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

        cin>>a[i];

    initrmq(n);

    while(q--)

    {

        int l, r, op;

        cin>>l>>r>>op;

        cout<<queryrmq(l,r,op)<<endl;

    }

}

巴特西

RMQ(Range MinimumQuery)问题之ST算法

ST算法------是用来求解给定区间RMQ的最值，本文以最小值为例

ST算法分为两部分

离线预处理（nlogn）：运用DP思想，用于求解区间最值，并保存到一个二维数组中。

在线查询 (O(1)）：对给定区间进行分割，借助该二维数组求最值

离线预处理

在线查询

最后上代码！

最新文章

热门文章