“聚二为一”
介绍
$ST$ 表是一种用来求 $RMQ$ ，即区间最值问题的数据结构。其速度极快，可以做到 $O(n \log n)$ 的预处理以及 $O(1)$ 的查询时，且可以在线查询。
$ST$ 表运用到了倍增的思想，将整个数列存储在一个二维数组 $f$ 中。其中：
$f_{i,j}$ 表示区间 $[f_{i,j},f_{i,i+2^j-1}]$ 的最值。
而查询的思路便是将区间分成左右两部分并取出两部分的最值。
对于区间 $[l,r]$ 的最大值，则是 $\max\{f_{l,k},f_{r-k+1,k}\}$，其中 $k$ 表示 $\log(r-l+1)$ 。
初始状态： $f_{i,0}=a_i$ ，然后外层遍历 $i$ ，内层遍历 $j$ 处理 $f$ 即可。
例题
【模板】ST表
区间最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
template<class T>
inline void underRead(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
int n,m,a[100001],f[100001][64],k[100001];
inline void underGet()
{
for(int i=1;i<=n;++i) k[i]=log2(i);
for(int i=1;i<=n;++i) f[i][0]=a[i];
for(int i=1;(1<<i)<=n;++i)
for(int j=1;j+(1<<i)-1<=n;++j)
f[j][i]=underMax(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
int main()
{
underRead(n),underRead(m);
for(int i=1;i<=n;++i) underRead(a[i]);
underGet();
for(int l,r;m;--m)
{
underRead(l),underRead(r);
printf("%d\n",underMax(f[l][k[r-l+1]],f[r-(1<<(k[r-l+1]))+1][k[r-l+1]]));
}
return 0;
}
|
练习
P2251 质量检测
P1816 忠诚