ST表¶

简介¶

ST表（Sparse Table，稀疏表）是一种基于倍增思想的数据结构，可以在 \(\Theta(n\log n)\) 时间内完成预处理，之后以 \(\Theta(1)\) 的时间复杂度回答每个询问，但不支持修改操作。

ST表主要用于解决 可重复贡献问题，例如区间最大值、最小值和区间最大公约数（GCD）等问题。

实现¶

以区间最大值为例，我们来讲解ST表的具体实现。

根据倍增思想，我们定义 \(f_{i,j}\) 表示从原数列第 \(i\) 位开始，长度为 \(2^j\) 的区间内的最大值。显然，当 \(j=0\) 时，\(f_{i,0} = a_i\)（即区间长度为1时的最大值就是元素本身）。

通过这个定义，我们可以发现任意一个区间都可以由至多两个预处理好的区间进行覆盖。

具体来说，对于一个区间 \([l, r]\)，我们可以将其分为两个可能重叠的子区间：

• \([l, l + 2^{\lfloor \log_2(r-l+1) \rfloor} - 1]\)
• \([r - 2^{\lfloor \log_2(r-l+1) \rfloor} + 1, r]\)

需要注意的是，这两个预处理出来的区间可能会有重叠部分，但根据上文中对于 可重复贡献问题 的定义，重叠部分并不影响答案的正确性。

数学表达如下：

综上，我们可以写出ST表初始化和查询的代码：

typedef unsigned long long ull;

// 快速计算 log2(x) 的向下取整值
inline ull fast_log2(ull x) {return 63 - __builtin_clzll(x);}

// 初始化
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) cin >> a[i][0];
for (int j = 1; j <= logN; ++j)
  for (int i = 0; i + (1 << j) - 1 < n; ++i)
    a[i][j] = max(a[i][j-1], a[i + (1 << (j-1))][j-1]);

// 查询
while (m--) {
  int l, r;
  cin >> l >> r;
  int log_k = fast_log2(r - l + 1);
  printf("%d\n", max(a[l][log_k], a[r - (1 << log_k) + 1][log_k]));
}

一些老教材中可能会提前预处理log数组，但实际上这样做不仅预处理时间更慢，而且还需要耗费大量的内存空间。在竞赛中，一般直接使用cmath库中的log2()函数或者上述代码中定义的ull fast_log2()函数来实现。

在所有实现方法中，上述代码中的fast_log2()函数是最快的。该函数通过__builtin_clzll(x)统计x的前导零的数量，在最终编译时只会编译为单条CPU指令，全程在寄存器内完成操作，速度甚至快于读取L1缓存。

需要注意的是，该函数仅能处理\(x>0\)的情况，__builtin_clzll(0)没有定义，返回值可能是任意值。同时，这种方法只能得到\(\log_2 x\)向下取整的结果，如果你需要浮点数运算，则不能使用该方法。

附¶

最后在这里丢一个区间信息维护的算法一览，以便读者对于这类题目所使用的算法的功能特性有较清晰的认识。