本文介绍了稀疏表的基本用法，以及如何在相关习题中应用它。
本文的简介部分主要参照了 $\text{OI WiKi}$ 的这篇文章。$\text{OI WiKi}$ 整合了各类有关编程竞赛的实用知识，感谢贡献者们！
为什么使用稀疏表？
稀疏表是用于解决 “可重复贡献问题” 的数据结构，什么是 “可重复贡献问题”？
若一个运算 ${\rm op}$ 满足 $x\,{\rm op}\,x=x$，则其对应的区间查询就是 “可重复贡献问题”。例如，最大值有 $\max(x,x)=x$，所以 RMQ 是这类问题；最大公约数有 $\gcd(x,x)=x$，区间最大公约数也是这类问题。区间和就不具备这个性质，如果求区间和所采用的区间有重叠，重叠部分就会被计算两次，这是我们不希望看到的。
另外，除了 RMQ、区间最大公约数以外，区间按位与、区间按位或等问题，都能够用稀疏表高效解决。这些问题都有着某种相似之处，例如区间按位与，就是每一位都取最小值；区间按位或，就是每一位都取最大值。
类似的解决这类问题的工具还有线段树。虽然稀疏表不支持修改操作，但是其查询时间被降至常数，在处理有大量询问的问题时十分有效。
| | 初始化 | 区间查询 | 单节点修改 |
|---|
| 线段树 | $O(n)$ | $O(\log n)$ | $O(\log n)$ |
| 稀疏表 | $O(n\log n)$ | $O(1)$ | 不可 |
如何使用稀疏表？
稀疏表使用 $O(n\log n)$ 的时间，预处理出一张二维的表格 $f(i,j)$ 。接下来以区间最大值为例，$f(i,j)$ 的含义为 “区间 $[i,i+2^j)$ 上的最大值”。
假设原数列为 $a$，显然有 $f(i,0)=a_i$ 。之后使用状态转移方程 $f(i,j)=\max\{f(i,j-1),f(i+2^{j-1},j-1)\}$ 填充完整张表格即可完成预处理。
若要查询区间 $[l,r)$ 上的最大值，返回 $\max\{f(l,s),f(r-2^s,s)\}$ 即可，其中 $s=\lfloor\log_2(r-l)\rfloor$ 。
给出一个序列，每次询问要求回答出某个区间中最大值和最小值之差。
题解
模板题，需要维护两张稀疏表，一张用于查询区间最大值，另一张用于查询区间最小值。查询后相减得到答案。
参考代码
P2880.cpp1
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
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 50001;
const int lg2maxn = 16;
int f[maxn][lg2maxn][2], lg2[maxn];
int main()
{
int n, q, l, r;
scanf("%d%d", &n, &q);
for (int i = 2; i <= n; ++i)
lg2[i] = lg2[i >> 1] + 1;
for (int i = 0; i != n; ++i)
scanf("%d", &f[i][0][0]), f[i][0][1] = f[i][0][0];
for (int j = 1; j <= lg2[n]; ++j)
for (int i = n - (1 << j); i != -1; --i)
f[i][j][0] = min(f[i][j - 1][0], f[i + (1 << (j - 1))][j - 1][0]);
for (int j = 1; j <= lg2[n]; ++j)
for (int i = n - (1 << j); i != -1; --i)
f[i][j][1] = max(f[i][j - 1][1], f[i + (1 << (j - 1))][j - 1][1]);
while (q--) {
scanf("%d%d", &l, &r), --l;
int s = lg2[r - l];
printf("%d\n", max(f[l][s][1], f[r - (1 << s)][s][1]) - min(f[l][s][0], f[r - (1 << s)][s][0]));
}
}
|
“$X$ 年是自 $Y$ 年以来降雨量最多的”，它的含义是 $X$ 年的降雨量不超过 $Y$ 年，且对于任意 $Y\lt Z\lt X$，$Z$ 年的降雨量严格小于 $X$ 年。给出两个年份，判断 “$X$ 年是自 $Y$ 年以来降雨量最多的” 这句话是否正确。由于有些年份的降雨量未知，有的说法是可能正确也可以不正确的。
题解
这题中稀疏表的地位很明确——只是个小工具，用于查询 $X$ 和 $Y$ 年之间的最大降雨量。这题的重头戏在于有些年份的降雨量是未知的，所以回答可能是 “无法判断”。
代码中的关键点、我曾经忘记考虑的点，都补上了注释，便于查看。
参考代码
LOJ2279.cpp1
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
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
using namespace std;
const int maxn = 50001;
const int lg2maxn = 16;
int n, q;
int key[maxn], val[maxn], f[maxn][lg2maxn], lg2[maxn];
int intvmax(int x, int y)
{
if (x >= y)
return -1;
int s = lg2[y - x];
return max(f[x][s], f[y - (1 << s)][s]);
}
int judge(int x, int y)
{
int ix = lower_bound(key, key + n, x) - key,
iy = lower_bound(key, key + n, y) - key;
if (key[ix] == x) {
int q = intvmax(ix + 1, iy);
if (key[iy] == y) {
if (val[iy] > val[ix])
return -1;
if (val[iy] > q) {
if (iy - ix == y - x)
return 1;
return 0;
}
return -1;
}
if (val[ix] > q)
return 0;
return -1;
}
if (key[iy] == y) {
if (iy <= ix)
return 0;
int q = intvmax(ix, iy);
if (val[iy] > q)
return 0;
return -1;
}
return 0;
}
int main()
{
scanf("%d", &n);
for (int i = 2; i <= n; ++i)
lg2[i] = lg2[i >> 1] + 1;
for (int i = 0; i != n; ++i)
scanf("%d%d", &key[i], &val[i]), f[i][0] = val[i];
for (int j = 1; j <= lg2[n]; ++j)
for (int i = n - (1 << j); i != -1; --i)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
scanf("%d", &q);
int x, y;
while (q--) {
scanf("%d%d", &x, &y);
int flag = judge(x, y);
if (flag == 1)
puts("true");
else if (flag == 0)
puts("maybe");
else
puts("false");
}
}
|