P3865 ST表

题意

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

对于 $100\%$ 的数据，满足 $1\le N\le {10}^5$，$1\le M\le 2\times{10}^6$，$a_i\in[0,{10}^9]$，$1\le l_i\le r_i\le N$。

思路

什么是ST表

ST表，是一种用来处理**RMQ（区间最值问题）**的算法。ST表可以做到 $\mathcal{O}(n\log{n})$ 预处理，之后 $\mathcal{O}(1)$ 查询, ST表的空间复杂度也是 $\mathcal{O}(n\log{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})$

$\underbrace{i,i+1,i+2,\cdots,i+2^{j-1}-1}_{\text{max里的第一部分}}\underbrace{,i+2^{j-1},i+2^{j-1}+1,\cdots,i+2^{j-1}+2^{j-1}-1}_{\text{max里的第二部分}}$

这样就可以从小合大了。

查询

查询的话也很简单，求一下 $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("%lld\n", query(l,r));
    }
    return 0;
}
复制代码