ST表

ST表利用了动态规划与倍增的思想,常用于解决RMQ(Range Minimum/Maximum Query区间最值问题),预处理复杂度$O(n\log n)$,查找复杂度$O(1)$。ST表并不支持在线修改,但对于端点位置的插入我们依然可以去维护其在这一点的性质而不去破坏整体结构的完整。

对于最大值问题,我们可以定义$Max[i][j]$数组,其表示$i\to i+2^j-1$位置的最大值,其中$j$的大小需要估算。

在预处理过程中,我们将区间长度$j$定义为阶段,代表以$i$为起点长度为$2^j$的长度的区间的最值。

对于每一次迭代,更新$Max[i][j]=max(Max[i][j-1],Max[i+2^{j-1}][j-1])$,更新为二分之后左右两个区间的最大值。

在查询的过程中,我们只需要对区间长度求对数(以2为底数),查询以左端点为起始点的最值与以右端点减取对数后的值为起始点的最值,并取这两个点的最值即可实现$O(1)$查询。这么做的原因是因为所要求解的区间长度可能并不为2的幂次,如此操作可以保证左右端点都被覆盖到。

参考代码如下:

//luogu P3865
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 1;
int n,m;

int Max[N][21];

int query(int l, int r) {
    int k = log2(r - l + 1);

    return max(Max[l][k], Max[r - ( 1 << k ) + 1][k]);
}

int main() {
    scanf("%d%d", &n, &m);
    for ( int i = 1; i <= n; ++i ) 
        scanf("%d", &Max[i][0]);

    for( int j = 1; j <= 21; j++ )
        for( int i = 1; i + ( 1 << j ) - 1 <= n; i++ )
            Max[i][j] = max(Max[i][j-1], Max[i + ( 1 << ( j - 1 ))][j-1]);

    int l,r;
    for ( int i = 1; i <= m; ++i ) {
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }

    return 0;
}
Last modification:October 15th, 2019 at 04:27 pm
博客维护不易,如果你觉得我的文章有用,请随意赞赏

One comment

  1. xstater

    妙!

Leave a Comment