RMQ问题的ST稀疏表解法

RMQ问题(Random Minimum/Maximum Query, 即区间最值问题)，指的是给定一个长度为n的数列A，对于A数列进行若干次询问，询问在闭区间[l, r]之中的最小/最大值是多少。RMQ问题有很多种解法，包括朴素算法、线段树、ST算法等，本文主要介绍使用ST稀疏表算法。

ST算法思想

ST(Sparse Table, 稀疏表)可以以O(nlogn)的时间效率对RMQ问题进行预处理，然后以O(1)的时间效率回答每个问题。
ST算法的实质是一种动态规划算法，我们定义了状态数组dp[i][j]表示从数组下标i开始包含$2^j$个数组元素在内的子数组中最小/大值。则此时，假设我们令$dp[1][0] = 2$, $dp[2][0] = 3$,则$dp[1][1] = min(dp[1][0], dp[2][0])$。即当我们需要求$dp[i][j+1]$的时候，我们可以将这一段子数组分成两段，分别求取两段的最值$dp[i][j]$和$dp[i+2^j][j]$，最后取这两个的最值的比较结果就可以得到结果。所以预处理的状态转移方程为$$dp[i][j+1] = min(dp[i][j], dp[i+2^j][j])$$
只要初始化当$j==0$的时候，最值是本身就可以很轻松的完成预处理。
针对题目要求，求取对任意给定的闭区间[l,r]中的最值，我只要找到小于这个区间长度的最大的2的非负整数次幂——T，分别求取前一段$dp[l][T]$和后一段$dp[r - s^T + 1][T]$最后进行比较就可以得出整个区间的结果，所以$$RMQ(l, r) = min(dp[l][T], dp[r - 2^T + 1][T])$$
其中$T = log_2(r-l+1)$。

题目要求

【输入】
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为一个整数N，意义如前文所述。
每组测试数据的第2行为N个整数，分别描述每种商品的重量，其中第i个整数表示标号为i的商品的重量weight_i。
每组测试数据的第3行为一个整数Q，表示小Hi总共询问的次数。
每组测试数据的第N+4~N+Q+3行，每行分别描述一个询问，其中第N+i+3行为两个整数Li, Ri，表示小Hi询问的一个区间[Li, Ri]。
对于100%的数据，满足N<=10^6，Q<=10^6, 1<=Li<=Ri<=N，0<weight_i<=10^4。
【输出】
对于每组测试数据，对于每个小Hi的询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：标号在区间[Li, Ri]中的所有商品中重量最轻的商品的重量。
【样例输入】

【样例输出】

最终代码

#include <iostream>
#include <algorithm>
using namespace std;
#define N 1000010

int dp[N][20];

int main()
{
    int n, m, next;
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> dp[i][0];

    int k = log2(n);
    for(int j = 1; j <= k; ++j)
    {
        for(int i = 0; i+(1<<j)-1 < n; ++i)
        {
            next = i + (1<<(j-1));
            dp[i][j] = min(dp[i][j-1], dp[next][j-1]);
        }
    }

    cin >> m;
    int l, r;
    while(m--)
    {
        cin >> l >> r;
        l--;
        r--;
        k = log2(r - l + 1);
        cout << min(dp[l][k], dp[r - (1<<k) + 1][k]) << endl;
    }
    return 0;
}

总结

位运算在算法中使用得当会有非常神奇的效果！！

使用using namespace std之后可以直接调用min(),max()功能函数，同时也不可以再以“max”或者“min”为变量名或函数名声明新的变量、函数。