P3865 ST表 学习笔记

题意

给定一个长度为 (N) 的数列，和 (M) 次询问，求出每一次询问的区间内数字的最大值。

对于 (100%) 的数据，满足 (1le Nle {10}^5)，(1le Mle 2times{10}^6)，(a_iin[0,{10}^9])，(1le l_ile r_ile N)。

思路

什么是ST表

ST表，是一种用来处理RMQ（区间最值问题）的算法。ST表可以做到 (mathcal{O}(nlog{n})) 预处理，之后 (mathcal{O}(1)) 查询, ST表的空间复杂度也是 (mathcal{O}(nlog{n})) 的。

如何实现ST表和它的原理

预处理

我们定义 (ST_{i,j})，为从第 (i) 个位置开始之后的 (2^j) 个位置的区间最大值。 我们知道：(2^k=2^{k-1}+2^{k-1})，所以在预处理时也一样。ST表有些类似于dp的思想。 (ST_{i,j}=max(ST_{i,j-1},ST_{i+2^{j-1},j-1}))

这样就可以从小合大了。

查询

查询的话也很简单，求一下 (k= log{(r-l+1)})，也就是区间长度的覆盖。然后因为向下取整，不可以直接 (ST_{l,k})，而是要用 (r-2^k+1) 重叠上去。不明白 (r-2^k+1)的话就是从终点开始往中心走那么多格子，这样的话一定可以和 (ST_{l,k}) 接上。

tips

需要注意一些边界，预处理的时候不要少处理，空间也要预留够。

代码

#include<cstdio>
#include <set>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const ll MAXN=1e5+5;
ll st[MAXN][40];
ll query(ll l,ll r){
    ll k= ll(log2(r-l+1));
    return max(st[l][k],st[r-(1<<k)+1][k]);
}
ll n,m,l,r;
int main(){
    cin>>n>>m;
    for (int i = 1; i <=n ; ++i) {
        scanf("%lld",&st[i][0]);
    }
    for (int k = 1; k <=log2(MAXN) ; ++k) {
        for (int i = 1; i+(1<<k)-1<=n ; ++i) {
            st[i][k]= max(st[i][k-1],st[i+(1<<(k-1))][k-1]);
        }
    }
    for (int i = 1; i <=m ; ++i) {
        scanf("%lld%lld",&l,&r);
        printf("%lldn", query(l,r));
    }
    return 0;
}