Dp-ST表（求解RMP）

RMQ（Range Minimum/Maximum Query）即区间最值查询：
对于长度为n的数列A，求解若干RMQ(i, j) (i,j<=n),返回A[i]~A[j]的最值。
ST（Sparse Table）可在线处理RMQ问题，可以在O（nlogn）内进行预处理，然后在O(1)内查询。

感谢优秀博客（写的很详细，这里只稍作总结）:
https://www.jianshu.com/p/8eebc50ad28a
https://www.cnblogs.com/zyf0163/p/4782133.html

算法思想

  1. 预处理（O(nlogn)）

· 确定数列A[i]至A[j]的最值，两重循环n^2复杂度，dp的思想是:
dp[i][j] 记录第i位~第i位开始的连续2^j位中的最值，dp[i][j]维护的区间是[i,i+2^j-1],构建的过程将区间分成两半，转移方程如下

dp[i][j]=max/min(dp[i][j-1], dp[i+2^(j-1)][j-1])

代码如下：

1
2
3
4
5
6
7
8
9
10
11
void ST(int n)
{
    for(int j = 1; (1<<j) <= n; ++j)
    {
        for(int i = 1; i+(1<<j)-1 <= n; ++i)
        {
            maxn[i][j] = max(maxn[i][j-1], maxn[i+(1<<(j-1))][j-1]);
            minn[i][j] = min(minn[i][j-1], minn[i+(1<<(j-1))][j-1]);
        }
    }
}

当然还有输入时的预处理

1
2
3
4
5
6
for(int i = 1; i <= n; ++i)
{
    int t;
    cin >> t;
    maxn[i][0] = minn[i][0] = t;
}
  1. 查询(O(1))
  • 查询区间[i, j]的最值
    ·然而dp能得到[i, i+2^j-1]的最值，这里很容易想到利用k=log2(j-i+1),求dp[i][k]就可以吗？
    没那么简单，k要取整所以dp范围会缩小，这里返回的是

    return max(dp[i][k], dp[j-2^k+1][k])

维护两区间[i][i+2^k-1], [j-2^k+1][j]，毫无疑问如果两区间有交集，即i+2^k-1 <= j-2^k+1这么返回就没问题,关于证明，参考的第二篇博客写的很清楚，这里不再赘述。
————————————————代码如下——————————————————————

1
2
3
4
5
6
7
void solve(int i, int j)
{
    int k = log2(j-i+1.0);    
    //int k = log(j-i+1.0) / log(2.0);
    cout << "max:" << max(maxn[i][k], maxn[j-(1<<k)+1][k]) << endl;
    cout << "min:" << min(minn[i][k], minn[j-(1<<k)+1][k]) << endl;
}

——————————————————完整代码——————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
int n, q;   //n个数里查找q次
typedef long long ll;
const int N = 100005;
int maxn[N][25];
int minn[N][25];
void ST(int n)
{
    for(int j = 1; j <= 20; ++j)
    {
        for(int i = 1; i+(1<<j)-1 <= n; ++i)
        {
            maxn[i][j] = max(maxn[i][j-1], maxn[i+(1<<(j-1))][j-1]);
            minn[i][j] = min(minn[i][j-1], minn[i+(1<<(j-1))][j-1]);
        }
    }
}
void solve(int i, int j)
{
    int k = log2(j-i+1.0);    
    //int k = log(j-i+1.0) / log(2.0);
    cout << "max:" << max(maxn[i][k], maxn[j-(1<<k)+1][k]) << endl;
    cout << "min:" << min(minn[i][k], minn[j-(1<<k)+1][k]) << endl;
}
int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; ++i)
    {
        int t;
        cin >> t;
        maxn[i][0] = minn[i][0] = t;
    }
    ST(n);
    for(;;)
    {
        int x, y;
        cin >> x >> y;
        solve(x, y);
    }
    return 0;
}