范围最值查询

Sparse Table

创建一个二维数组 ${\displaystyle F[1\dots N][0\dots O(\log _{2}N)]}$  的整数值。

在这个数组中 ${\displaystyle F[i][j]}$  表示范围 ${\displaystyle [i,i+2^{j}-1]}$  中的最大值（例如 ${\displaystyle [2,5]}$  中的最大值被计为 ${\displaystyle F[2][2]}$ ）。

创建数组的过程可以在 ${\displaystyle O(N\log N)}$  时间内完成。具体算法类似于动态规划。以下是 C++ 语言描述的代码，数组约定从 0 开始：

void Initialise(vector<int> &Array)
{
	int Length = (int)Array.size();

	// 长度为 0 时，表示数据自身。
	for (int i = 0; i < Length; ++i) F[i][0] = Array[i];
	
	for (int j = 1; (1 << j) <= Length; ++j)
		for (int i = 0; i + (1 << j) - 1 < Length; ++i)
			F[i][j] = min(
				F[i][j - 1], F[i + (1 << (j - 1))][j - 1]
			); // 分成长度相等的两段
}

当我们需要计算一个区间中的最大值（例如 ${\displaystyle [3,8]}$  时），我们先求出这个区间的长度（即 8 - 3 + 1 = 6）。

然后我们算出不大于它的最大 ${\displaystyle 2^{k}}$  值的指数（即 2）。我们要查询分别以 3 开头，和以 8 结尾的两个长度为 ${\displaystyle 2^{2}}$  的区间的最大值。

显然 ${\displaystyle F[3][2]}$  和 ${\displaystyle F[5][2]}$  也就是（${\displaystyle [3,6]}$  和 ${\displaystyle [5,8]}$ ）的最大值就是 ${\displaystyle [3,8]}$  的最大值。查询的时间是常数，代码如下：

int Query(int Left, int Right)
{
	int i = 0;
	
	while (1 << (i + 1) <= Right - Left + 1) ++i;
	
	return min(
		F[Left][i], F[Right - (1 << i) + 1][i]
	);
}

程序预处理的时间复杂度是 ${\displaystyle O(N\log N)}$ 的，单次询问的时间复杂度是${\displaystyle O(1)}$ 的。整个程序的空间复杂度是${\displaystyle O(N\log N)}$ 。

Method of Four Russians

Method of Four Russians（英语：Method of Four Russians）先对数组进行分块，再预处理出每个块里的ST表，以及每个块的最值构成的数组的ST表。然后每次查询时，只需算出中间连续几个块的最小值与两边不完整的块的最小值的最小值。程序预处理的时间复杂度是 ${\displaystyle O(N\log \log N)}$ 的，单次询问的时间复杂度是${\displaystyle O(1)}$ 的。整个程序的空间复杂度是${\displaystyle O(N\log \log N)}$ 。还可以再优化，使预处理的时间复杂度是 ${\displaystyle O(N)}$ 的，单次询问的时间复杂度是${\displaystyle O(1)}$ 的，空间复杂度是${\displaystyle O(N)}$ 。^[2]

如果使用线段树等数据结构，则可以做到预处理的时间复杂度是 ${\displaystyle O(N\log N)}$ ，单次询问的时间复杂度是${\displaystyle O(\log N)}$ 。整个程序的空间复杂度是${\displaystyle O(N)}$ 。优点是可以支持动态修改。

在Fischer和Heun（2007）中可以找到一些应用。^[3]:3

计算树中的最近公共祖先

范围最值查询可被用于解决最近公共祖先问题^[4][5]。有根树S中的节点v与w的最近公共祖先是在从根到w和v的路径上最深的公共节点u（其可能是v或w）。 Gabow, Bentley和Tarjan（1984）表明，最近公共祖先问题可以在线性时间内规约到范围最值查询问题。由此可见，与范围最值查询问题一样，最近公共祖先问题可以在常数时间内进行单次查询，并仅使用线性空间^[3]。