ST表

ST 表适用于解决可重复贡献问题．

ST 表使用倍增的思想．我们现在想要快速求序列 $a$ 中的区间最小值，需要维护以下数据：

• f[j][i]：从 i 开始，长度为 $2^j$ 的序列的最小值．

f 数组可以通过递推的方式预处理出来，每次计算 $[i, i+2^j-1]$ 的最小值时，可以拆分为 $[i, i+2^{j-1}-1]$ 和 $[i+2^{j-1}, 2^j-1]$ 这两个区间中的较小值，递推关系如下：

显然，初始条件为：$f[0][i] = a[i]$．预处理时间复杂度 $O(n\log n)$．

1
for (int i = 0; i <= n; i++) {
2
  st[0][i] = a[i];
3
}
4
for (int j = 1; j <= 17; j++) {
5
  for (int i = 1; i + (1 << j) - 1 <= n; i++) {
6
    st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
7
  }
8
}

在查询 $[l,r]$ 的最小值时，我们可以将长度 $s$ 取 $\log_2$．设结果为 $k$，则 $2^k$ 必定大于等于 $s$ 的一半，且小于 $s$．此时，答案为从 $l$ 开始，长度为 $2^k$ 的区间，和末尾为 $r$，长度为 $2^k$ 的区间的最小值．这两个区间的交集必然是 $[l,r]$．可以列出表达式：

查询复杂度是 $O(1)$ 的．

1
int query(int l, int r) {
2
    int len = log2(r - l + 1);
3
    return min(st[len][l], st[len][r - (1 << len) + 1]);
4
}