ST表 | Kyons'Blog

引例

洛谷P3865
$RMQ$的中文翻译为:静态区间最值查询.~~英文我不知道所以不写~~给你$n$个数,$m$次查询,查询的内容为区间$[l,r]$中的最大值.
$RMQ$有解法蛮多的,$st$表,线段树,树状数组,划分树都可以做.
$st$表的复杂度为预处理$O(n*{\log_2} n)$+查询$O(m)$
而线段树则需要预处理$O(n*{\log_2} n)$+查询$O(m*{\log_2} n)$
~~树状数组没学,不清楚~~
线段树可以看我之前的博客.

定义

这个算法就是基于$DP$和位运算符，我们用$dp[i][j]$表示从第 $i$ 位开始，到第 $i + 2^j -1$ 位的最大值或者最小值。

那么我求$dp[i][j]$的时候可以把它分成两部分，第一部分从 $i$ 到 $i + 2 ^{(j-1)} - 1$ ，第二部分从 $i + 2 ^{(j-1)}$ 到$i + 2^j- 1$,那么可以得到
$$dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1])$$
当$j=0$时,求的是长度为1的区间的最小值,
$j=1$时,求的是长度为2的区间最小值
$j=2$时,求的是长度为4的区间最小值
以此类推,故可在$O(n\log_2 n)$的复杂度处理完.
如图所示

查询的话,只需要反过来就阔以了.

完整代码

这里mm[i] = mm[i - 1] +((i&(i - 1)) == 0);

```cpp
const int MAXN = 1e5 + 10;

int dp[MAXN][31],a[MAXN],mm[MAXN];

void initRMQ(int n)
{
    mm[0] = -1;
    for (int i = 1; i <= n; i++) {
        mm[i] = mm[i - 1] +((i&(i - 1)) == 0);
        dp[i][0] = a[i];
    }
    for (int j = 1; j <= mm[n]; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}

int rmq(int x, int y)
{
    int k = mm[y - x + 1];
    return max(dp[x][k], dp[y - (1 << k) + 1][k]);
}

int main()
{
    int n,m;
    cin >> n >> m;//scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    initRMQ(n);

    while (m--) {
        int x, y;
        cin >> x >> y;
        cout << rmq(x, y) << '\n';
    }
    return 0;
}