ST表，又叫稀疏表，是一种利用倍增和动态规划实现O(nlogn)预处理，O(1)查找区间最值的数据结构。
主要是用于对付查询次数较多的情况，写起来也比线段树更加简便。
用F[i,j]表示以i为起点，长度为2^j的区间的最小值(当然也可以是最大值，这里用最小值举例)。
那么可以得出转移方程：F[i,j] = min(F[i,j-1], F[i + 1<<(j-1)][j-1])
初始化显然是F[i,0] = a[i]
实现查询区间(l,r)内最值的办法是把区间分成[l,l + 2^i]和[r - 2^i,r] 其中 l < 2^i < r。这里利用了最值区间重叠也没关系的性质。
可以预处理出所有数的log值，这样计算比较方便。
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
| #include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 100005;
int f[maxn][20];
int lg2[maxn];
int a[maxn];
int n,m;
int maxx(int a,int b)
{
return a>b?a:b;
}
inline void build_ST()
{
for (register int i = 1; i <= n; i++) f[i][0] = a[i];
for (int j = 1; j < 18; j++)
{
for (register int i = 1; i <= n - (1 << j - 1); i++)
{
f[i][j] = maxx( f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
for (register int i = 2; i <= n; i++)
lg2[i] = lg2[i>>1] + 1;
}
inline int rmq(int l,int r)
{
int t = lg2[r - l + 1];
return maxx(f[l][t], f[r - (1 << t) + 1][t]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
build_ST();
while(m--)
{
int l, r;
scanf("%d%d",&l,&r);
int ans = rmq(l,r);
printf("%d\n",ans);
}
return 0;
}
|