我来做最不想做的事情了——《22/7》

稀疏表

ST表（Spare Table，稀疏表）是一种简单的数据结构，主要用来解决RMQ（Range Maximum/Minimum Query，区间最大/最小值查询）问题。

RMQ问题，以最大值为例，假如有一个数列 ，给定一个区间 ，要求 。

朴素的想法是直接暴力遍历 区间，时间复杂度是 ，这个时间复杂度太糟糕了，特别是当查询很多次的时候，所以我们要对其进行改进。

倍增

还记得我们在《我的最近公共祖先一定有问题》里使用到的倍增思想吗，在树上每次向上跳 形式的节点数，一倍一倍向下降，只不过现在我们是线性结构，仍可以使用。

表使用一个二维数组 ，对于范围内的 ，先算出并存储 ，这是预处理。查询时，再利用这些子区间算出待求区间的最大值。

稀疏表的食用

预处理

为了减少时间复杂度，可以用动态规划的方法进行预处理：

1
2
3
4
5
6
int f[N][21];
for (int i = 1; i <= n; i ++)
	scanf ("%d", &f[i][0]);
for (int j = 1; j <= 21; j ++)
	for (int i = 1; i + (1 << j) - 1 <= N; i ++)
		f[i][j] = max (f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

一个很棒的演示图把区间平分为两部分，前半段按定义当然是从 到 的最大值，后半段则是从 到 的最大值。

每半段的长度是

查询

查询时，我们需要找到两个 的子区间，它们的并集恰是 （不必不相交）。具体地说，我们要找一个整数 ，两个子区间分别为 和 ，有点像下图：

少女寻找中…… 我们希望前一个子区间的右端点尽量接近 。当 有 ，这时 也成立。

但因为 是整数，所以我们取 。可以证明，这时两个子区间确实可以覆盖 。

在线查询的的代码如下：

1
2
3
4
5
6
for (int i = 1; i <= m; i ++)
{
	scanf ("%d %d", &l, &r);
	int k = log2 (r - l + 1);
	printf ("%d\n", max (f[l][k], f[r - (1 << k) + 1][k]));
}

表不仅能处理最大/最小值，凡是符合结合律且可重复贡献的信息查询都可以使用 表高效进行。设有一个二元运算 ，满足 ，则 是可重复贡献的，意义在于可以对两个交集不为空的区间进行信息合并。