ST 表

Sparse Table，稀疏表，主要用来解决区间最大、最小值查询问题。主要应用倍增思想，实现 O(nlogn)预处理，O(1)查询

不支持修改操作

基于倍增思想，我们考虑求出区间最大值，从最小的区间开始统计，然后再此基础上统计下一级区间，通过一遍一遍的预处理增大统计的步长，并整合各级区间的最大值

文字解释比较抽象，结合实现来看

实现

给出题目Luogu P3865 ST 表

引入二维数组 st[i][j]，即元素 i 左侧开始向右跳 1 << j 步所包含的区间中的最值

我们首先对每个最小单位进行初始化：

for (int i = 1; i <= N; i++)  // 每个点跳 1<<0 步的结果为本身
  cin >> st[i][j];

然后，我们可以枚举跳跃区间的步长和起点位置，通过递推来统计子区间的最值：

for (int j = 1; j <= 20; j++)                    // 枚举区间长度
        for (int i = 1; i + (1 << j) - 1 <= N; i++)  // 枚举起点
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); // 两个子区间极值的极值

这里注意要先枚举步长 j 以获得每一点跳跃 j-1 步所获得的极值，否则下面递推中的st[i + (1 << (j - 1))][j - 1]无法成立

至此，st 表构建完成，预处理结束

查询

接着，我们可以实现 O(1)复杂度的查询操作

先给出代码：

// 处理查询
    for (int i = 1; i <= M; i++) {
        int l, r;
        cin >> l >> r;
        int k = __builtin_log2(r - l + 1);
        cout << max(st[l][k], st[r - (1 << k) + 1][k]) << endl;
    }

这里int k = __builtin_log2(r - l + 1);操作是为了获取合适的步长区间，这样保证max(st[l][k], st[r - (1 << k) + 1][k])可以覆盖整个需要查询的区间