文章目录
一、介绍
1.作用——可重复贡献问题
对于操作
o
p
t
opt
opt，满足
∀
l
≤
k
≤
r
,
o
p
t
[
l
,
r
]
=
o
p
t
(
o
p
t
[
l
,
k
]
,
o
p
t
[
k
,
r
]
)
\forall l \leq k \leq r,opt[l,r]=opt( opt[l,k],opt[k,r])
∀l≤k≤r,opt[l,r]=opt(opt[l,k],opt[k,r])，例如
R
M
Q
RMQ
RMQ区间求最值，又如区间
G
C
D
GCD
GCD，都可以称为可重复贡献问题。
而ST表就是用于解决以
R
M
Q
RMQ
RMQ问题为代表的可重复贡献问题。
2.ST表的优劣
之前我们学习过线段树，同样可以用于解决
R
M
Q
RMQ
RMQ问题，与线段树相比，稀疏表的码量更少，但同样，稀疏表所适合的情况也更局限一些。
稀疏表包含两个过程，分别是预处理和查询，预处理的时间复杂度为
O
(
n
l
o
g
n
)
O(n\ logn)
O(n logn),而查询可以在
O
(
1
)
O(1)
O(1)内实现。
稀疏表的局限在于不支持在线修改，一旦预处理结束后，就只能对静态的区间进行查询（一般情况）。
二、实现（基于RMQ）
我们以 s t [ i ] [ j ] st[i][j] st[i][j]表示 m a x { a [ k ] ∣ i ≤ k ≤ i + 2 j − 1 } max\{a[k]\mid i\leq k \leq i+2^j-1\} max{a[k]∣i≤k≤i+2j−1}
1.预处理
思路与动态规划一致，自左向右，自上往下递推出结果。
需要注意一下计算顺序！！！
递推式：
s
t
[
i
]
[
j
]
=
m
a
x
(
s
t
[
i
]
[
j
−
1
]
,
s
t
[
i
+
(
1
<
<
(
j
−
1
)
)
]
[
j
−
1
]
)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1])
st[i][j]=max(st[i][j−1],st[i+(1<<(j−1))][j−1])
基于
∀
l
≤
k
≤
r
,
o
p
t
[
l
,
r
]
=
o
p
t
(
o
p
t
[
l
,
k
]
,
o
p
t
[
k
,
r
]
)
\forall l \leq k \leq r,opt[l,r]=opt( opt[l,k],opt[k,r])
∀l≤k≤r,opt[l,r]=opt(opt[l,k],opt[k,r])
for(int j=1;j<=logn;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
2.查询
若给定任意区间范围
[
l
,
r
]
[l,r]
[l,r]，如何根据
s
t
[
i
]
[
j
]
st[i][j]
st[i][j]求出对应结果？
a
n
s
=
m
a
x
{
s
t
[
l
]
[
k
]
,
s
t
[
r
−
(
1
<
<
k
)
+
1
]
[
k
]
}
ans=max\{st[l][k],st[r-(1<<k)+1][k]\}
ans=max{st[l][k],st[r−(1<<k)+1][k]}
s
t
[
l
]
[
k
]
st[l][k]
st[l][k]表示区间
[
l
,
l
+
2
k
−
1
]
[l,l+2^k-1]
[l,l+2k−1]
s
t
[
r
−
(
1
<
<
k
)
+
1
]
[
k
]
st[r-(1<<k)+1][k]
st[r−(1<<k)+1][k]表示区间
[
r
−
2
k
+
1
,
r
]
[r-2^k+1,r]
[r−2k+1,r]
为了保证区间的重叠，应满足
r
−
2
k
+
1
≤
l
+
2
k
−
1
r-2^k+1 \leq l+2^k-1
r−2k+1≤l+2k−1
化为:
r
−
l
2
+
1
≤
2
k
\frac{r-l}{2}+1\leq 2^k
2r−l+1≤2k
对式子两边取对数，
得：
l
o
g
2
(
r
−
l
2
+
1
)
≤
k
log_2(\frac{r-l}{2}+1)\leq k
log2(2r−l+1)≤k
若 k k k直接取 l o g 2 ( r − l 2 + 1 ) log_2(\frac{r-l}{2}+1) log2(2r−l+1),可以得到一个唯一的中间点 r + l 2 \frac{r+l}{2} 2r+l，看上去这应该是理想的值，但实际上我们很难使得 k k k恰好等于 l o g 2 ( r − l 2 + 1 ) log_2(\frac{r-l}{2}+1) log2(2r−l+1)，首先是计算 r − l 2 \frac{r-l}{2} 2r−l要考虑结果会自动舍去小数部分，其次是计算对数也需要化为整型，依然会舍去小数部分，这些都会使得最终计算出来的 k k k小于 l o g 2 ( r − l 2 + 1 ) log_2(\frac{r-l}{2}+1) log2(2r−l+1)。
所以我们令 k k k等于 l o g 2 ( r − l + 1 ) log_2(r-l+1) log2(r−l+1),不必考虑除法计算，虽然计算过程中仍然要考虑对数化为整型的情况，但可以保证两个子区间可以覆盖大的区间。
3.对数优化
过程中需要多次使用log，本来可以直接使用
S
T
L
STL
STL中的函数，但为了避免超时，可以直接打表。
l
o
g
[
i
]
=
{
−
1
i
=
0
l
o
g
[
i
2
]
+
1
i
>
0
log[i]=\begin{cases} -1 & i=0 \\ log[\frac{i}{2}]+1 & i>0\\ \end{cases}
log[i]={−1log[2i]+1i=0i>0
4.模板代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int logn=log2(N);
int n,m;
int st[N][logn];
int Logn[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
int main(){
n=read();
m=read();
Logn[0]=-1;
for(int i=1;i<=n;i++){
st[i][0]=read();
Logn[i]=Logn[i/2]+1;//计算以2为底的对数
}
for(int j=1;j<=logn;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
}
int l,r,k;
while(m--){
l=read();
r=read();
k=Logn[r-l+1];
printf("%d\n",max(st[l][k],st[r-(1<<k)+1][k]));
}
}