#c

C++倍增法基础——ST表

高效区间最值查询的进阶算法

#c
@鞠大龙
魅客科创中心

CONTENTS

目录

1. RMQ问题概述

1.1 RMQ问题定义

区间最值查询(RMQ)问题：

  • 问题定义：给定一个长度为n的数组arr和多个查询(l, r)，每次查询需要返回arr[l...r]中的最小值或最大值
  • 输入格式：数组arr[0...n-1]，查询(l, r)表示查询区间[l, r]
  • 输出格式：返回区间[l, r]的最小值或最大值

示例：

  • 数组：arr = [3, 1, 4, 1, 5, 9, 2, 6]
  • 查询(2, 5)：返回1（区间[2, 5] = [4, 1, 5, 9]的最小值）
  • 查询(1, 6)：返回1（区间[1, 6] = [1, 4, 1, 5, 9, 2]的最小值）
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

1.2 解决RMQ问题的方法对比

朴素算法：

  • 方法：每次查询都遍历整个区间
  • 预处理：O(1)
  • 单次查询：O(n)
  • 适用场景：查询次数很少的情况

线段树：

  • 方法：构建线段树，支持区间查询和单点更新
  • 预处理：O(n)
  • 单次查询：O(log n)
  • 适用场景：需要动态更新的情况

ST表（倍增法）：

  • 方法：预处理所有2^j长度的区间，查询时分解为两个重叠区间
  • 预处理：O(n log n)
  • 单次查询：O(1)
  • 适用场景：静态数组，大量查询

选择建议：

  • 静态数组 + 大量查询 → ST表
  • 动态数组 + 频繁更新 → 线段树
  • 查询次数很少 → 朴素算法
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

1.3 ST表的核心思想

ST表的核心思想：

  1. 基于倍增思想：

    • 预处理所有长度为2^j的区间
    • 利用2的幂次性质进行区间分解

  2. 可重叠查询：

    • 允许查询区间重叠
    • 用两个2^k长度区间覆盖查询区间

  3. 静态数组：

    • 预处理后不修改
    • 适合静态数据的场景

关键观察：

  1. 2的幂次覆盖：

    • 任何区间都可以被2的幂次长度区间覆盖
    • 最多需要2个2^k长度区间

  2. 重叠保证：

    • 两个2^k长度区间必然有重叠
    • 重叠部分不影响最值查询结果

  3. 预处理效率：

    • 利用动态规划快速预处理
    • 空间换时间，查询O(1)
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

2. ST表原理与推导

2.1 ST表的数学基础

区间长度与2的幂次：

设区间长度为

找到最大的 使得

则

查询区间分解：

查询区间 可以分解为：

  • 和
  • 这两个区间都有长度
  • 两个区间必然有重叠，覆盖整个查询区间

ST表定义：

令 表示从位置 开始，长度为 的区间最小值。

初始状态：

  • （长度为1的区间）

递推公式：

对于 ：

返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

2.2 ST表递推关系推导

递推关系推导：

长度为 的区间 可以分成：

  • 左半部分：，长度为
  • 右半部分：，长度为

因此：
左半部分最小右半部分最小

推导总结：

  • 将大问题分解为两个小问题
  • 小问题的区间长度减半
  • 通过递推关系构建完整ST表

递推关系可视化：

区间长度：2^j = 2^3 = 8
[i, i+7] = [i, i+3] ∪ [i+4, i+7]

st[i][3] = min(st[i][2], st[i+4][2])

区间长度：2^2 = 4
[i, i+3] = [i, i+1] ∪ [i+2, i+3]

st[i][2] = min(st[i][1], st[i+2][1])
st[i+4][2] = min(st[i+4][1], st[i+6][1])

递推的关键：

  • 每次将区间长度减半
  • 利用已计算的小区间计算大区间
  • 通过动态规划实现高效预处理
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

2.3 ST表查询推导

查询算法推导：

给定查询区间 ，需要找到最小值。

  1. 计算区间长度：

  2. 找到最大的2的幂：

  3. 分解查询区间：

重叠证明：

设 ，其中

查询区间：

左区间：

右区间起点：

右区间：

重叠条件：

即：

由于 ，条件成立！

返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

2.4 ST表查询公式

查询公式：

其中

时间复杂度：

  • 预处理：
  • 查询：
  • 空间：

空间复杂度分析：

ST表需要存储：

  • 个起始位置
  • 对于每个位置，存储 个不同长度的区间
  • 总共需要 个元素
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

2.5 log2数组的预计算

为什么要预计算log2？

  • 避免每次查询都调用log函数
  • log函数的计算开销较大
  • 预计算后查询更快

log2数组定义：

表示 的向下取整

递推公式：

边界条件：

log2数组示例：

i:      1  2  3  4  5  6  7  8  9 10
log2[i]:0  1  1  2  2  2  2  3  3  3

预计算代码：

vector<int> log2(n + 1);
log2[1] = 0;
for (int i = 2; i <= n; i++) {
    log2[i] = log2[i / 2] + 1;
}

使用示例：

查询长度为6的区间：

  • 使用长度为4的区间
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

2.6 ST表完整构建示例

构建示例：

给定数组

第一步：初始化（j=0）

st[i][0] = arr[i]
st[0][0] = 3
st[1][0] = 1
st[2][0] = 4
st[3][0] = 1
st[4][0] = 5
st[5][0] = 9
st[6][0] = 2
st[7][0] = 6

第二步：计算j=1（长度为2）

st[i][1] = min(st[i][0], st[i+1][0])

st[0][1] = min(3, 1) = 1
st[1][1] = min(1, 4) = 1
st[2][1] = min(4, 1) = 1
st[3][1] = min(1, 5) = 1
st[4][1] = min(5, 9) = 5
st[5][1] = min(9, 2) = 2
st[6][1] = min(2, 6) = 2

第三步：计算j=2（长度为4）

st[i][2] = min(st[i][1], st[i+2][1])

st[0][2] = min(1, 1) = 1
st[1][2] = min(1, 1) = 1
st[2][2] = min(1, 5) = 1
st[3][2] = min(1, 2) = 1
st[4][2] = min(5, 2) = 2

第四步：计算j=3（长度为8）

st[i][3] = min(st[i][2], st[i+4][2])

st[0][3] = min(1, 2) = 1

ST表完整形式：

        j=0  j=1  j=2  j=3
i=0:     3    1    1    1
i=1:     1    1    1   -
i=2:     4    1    1   -
i=3:     1    1    1   -
i=4:     5    5    2   -
i=5:     9    2    -   -
i=6:     2    2    -   -
i=7:     6    -    -   -
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

3. ST表代码实现

3.1 ST表基础模板

// 稀疏表(Sparse Table)用于解决RMQ(区间最值查询)问题
class SparseTable {
private:
    vector<vector<int>> st;  // st[i][j]表示从i开始长度为2^j的区间的最小值
    vector<int> log2;        // log2[i]表示log2(i)的向下取整
    int n;                   // 数组长度

public:
    SparseTable(const vector<int>& arr) {
        n = arr.size();

        // 预计算log2数组
        log2.resize(n + 1);
        log2[1] = 0;
        for (int i = 2; i <= n; i++) {
            log2[i] = log2[i/2] + 1;
        }

        // 构建稀疏表
        int logN = log2[n] + 1;
        st.resize(n, vector<int>(logN));

        // 初始化长度为1的区间
        for (int i = 0; i < n; i++) {
            st[i][0] = arr[i];
        }

        // 动态规划构建稀疏表
        for (int j = 1; j < logN; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1]);
            }
        }
    }

    // 查询区间[l, r]的最小值，O(1)时间
    int queryMin(int l, int r) {
        int j = log2[r - l + 1];
        return min(st[l][j], st[r - (1 << j) + 1][j]);
    }
};
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

3.2 ST表完整模板（通用版）

#include <bits/stdc++.h>
using namespace std;

// ST表模板 - 支持任意可结合运算
template<typename T, typename Combine>
class SparseTable {
private:
    vector<vector<T>> st;
    vector<int> log2;
    int n;
    Combine combine;
    
public:
    SparseTable(const vector<T>& arr, Combine cmp) : combine(cmp) {
        n = arr.size();
        
        // 预计算log2数组
        log2.resize(n + 1);
        log2[1] = 0;
        for (int i = 2; i <= n; i++) {
            log2[i] = log2[i / 2] + 1;
        }
        
        // 构建稀疏表
        int logN = log2[n] + 1;
        st.resize(n, vector<T>(logN));
        
        // 初始化长度为1的区间
        for (int i = 0; i < n; i++) {
            st[i][0] = arr[i];
        }
        
        // 动态规划构建
        for (int j = 1; j < logN; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = combine(st[i][j-1], st[i + (1 << (j-1))][j-1]);
            }
        }
    }
    
    // 查询区间[l, r]
    T query(int l, int r) {
        int j = log2[r - l + 1];
        return combine(st[l][j], st[r - (1 << j) + 1][j]);
    }
};

// 使用示例
int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // 求最小值
    auto minFunc = [](int a, int b) { return min(a, b); };
    SparseTable<int, decltype(minFunc)> stMin(arr, minFunc);
    
    // 求最大值
    auto maxFunc = [](int a, int b) { return max(a, b); };
    SparseTable<int, decltype(maxFunc)> stMax(arr, maxFunc);
    
    // 查询示例
    cout << "区间[2, 5]的最小值: " << stMin.query(2, 5) << endl;
    cout << "区间[0, 7]的最大值: " << stMax.query(0, 7) << endl;
    
    return 0;
}
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

3.3 ST表求最大公约数(GCD)

GCD的性质：

ST表不仅适用于最值查询，还适用于任何满足结合律的运算，如GCD。

GCD的结合律：

因此ST表的递推公式同样适用：

实现代码：

// GCD的ST表实现
class GCDSparseTable {
private:
    vector<vector<int>> st;
    vector<int> log2;
    int n;
    
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
public:
    GCDSparseTable(const vector<int>& arr) {
        n = arr.size();
        
        // 预计算log2
        log2.resize(n + 1);
        log2[1] = 0;
        for (int i = 2; i <= n; i++) {
            log2[i] = log2[i/2] + 1;
        }
        
        // 构建ST表
        int logN = log2[n] + 1;
        st.resize(n, vector<int>(logN));
        
        for (int i = 0; i < n; i++) {
            st[i][0] = arr[i];
        }
        
        for (int j = 1; j < logN; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = gcd(st[i][j-1], st[i + (1 << (j-1))][j-1]);
            }
        }
    }
    
    int query(int l, int r) {
        int j = log2[r - l + 1];
        return gcd(st[l][j], st[r - (1 << j) + 1][j]);
    }
};

GCD查询示例：

给定数组

构建ST表：

j=0: [12, 18, 24, 30, 36]
j=1: [6, 6, 6, 6] (gcd(12,18)=6, gcd(18,24)=6, ...)
j=2: [6, 6]

查询区间[1, 3]的GCD：

  1. 区间长度：
  3. 分解：
    • 左区间：
    • 右区间：
  4. 查询：

验证：
区间的元素：
✓

复杂度：

  • 预处理：
  • 单次GCD查询：
  • 总查询复杂度：（忽略GCD本身的复杂度）
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

4. ST表应用实例

4.1 ST表查询示例

查询示例1：查询区间[2, 5]的最小值

步骤分析：

  1. 区间长度：

  2. 计算k值：

  3. 分解区间：

    • 左区间：
    • 右区间：

  4. 查询结果：

验证：
区间元素：
最小值确实是1

查询示例2：查询区间[1, 6]的最小值

  1. 区间长度：

  2. 计算k值：

  3. 分解区间：

    • 左区间：
    • 右区间：

  4. 查询结果：

可视化查询过程：

数组：      3, 1, 4, 1, 5, 9, 2, 6
索引：     0  1  2  3  4  5  6  7

查询[2, 5]：
        [2, 5]长度=4
        k=2, 2^k=4

        左区间[2,5]:  ━━━━━━
        右区间[2,5]:        ━━━━━━

        重叠部分保证覆盖

查询[1, 6]：
        [1, 6]长度=6
        k=2, 2^k=4

        左区间[1,4]:  ━━━━━━
        右区间[3,6]:         ━━━━━━
                        ━━━━━━ (重叠)

        两个区间覆盖[1,6]

log2数组预计算：

为了避免每次查询都计算log2，我们预计算：

log2[1] = 0
log2[2] = 1
log2[3] = 1
log2[4] = 2
log2[5] = 2
log2[6] = 2
log2[7] = 2
log2[8] = 3
...

递推公式：

返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

4.2 RMQ问题的ST表解决方案

问题描述：
给定一个长度为n的数组arr和多个查询(l, r)，每次查询需要返回arr[l...r]中的最小值。

预处理步骤：

  1. 初始化ST表：st[i][0] = arr[i]（长度为1的区间）
  2. 使用动态规划填充ST表：
    • st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1])
    • 即：区间[i, i+2^j-1]的最小值 = min(区间[i, i+2^(j-1)-1]的最小值, 区间[i+2^(j-1), i+2^j-1]的最小值)

查询步骤：

  1. 计算区间[l, r]的长度：len = r - l + 1
  2. 找到不超过len的最大2的幂：j = log2(len)
  3. 将区间分解为两个长度为2^j的重叠区间：
    • [l, l+2^j-1]和[r-2^j+1, r]
  4. 返回这两个区间最小值的较小者：
    • min(st[l][j], st[r-(1<<j)+1][j])

示例：

考虑数组arr = [3, 1, 4, 1, 5, 9, 2, 6]

预处理ST表（部分）：

  • st[i][0] = arr[i]
  • st[0][1] = min(st[0][0], st[1][0]) = min(3, 1) = 1
  • st[1][1] = min(st[1][0], st[2][0]) = min(1, 4) = 1
  • ...
  • st[0][2] = min(st[0][1], st[2][1]) = min(1, 1) = 1
  • ...

查询区间[2, 5]的最小值：

  1. len = 5 - 2 + 1 = 4
  2. j = log2(4) = 2
  3. 两个重叠区间：[2, 2+2^2-1] = [2, 5]和[5-2^2+1, 5] = [2, 5]
  4. 结果 = min(st[2][2], st[2][2]) = min(1, 1) = 1

复杂度分析：

  • 预处理时间复杂度：O(n log n)
  • 查询时间复杂度：O(1)
  • 空间复杂度：O(n log n)
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

5. ST表的局限性与对比

5.1 ST表的局限性

ST表的局限性

  • 静态数据：ST表不支持动态修改，一旦构建完成，数组不能改变
  • 空间复杂度：需要的额外空间，对于大规模数据可能有压力
  • 仅适用于可重叠查询：有些问题要求不重叠区间，ST表不适用
  • 不适合单点更新：如果需要频繁单点更新，应该使用线段树等数据结构
  • 不满足结合律的运算：如减法、除法等不满足结合律，无法使用ST表
  • 预处理开销：对于查询次数很少的情况，预处理开销可能不值得
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

5.2 ST表与线段树对比

ST表优势：

  1. 查询速度快：查询，线段树需要
  2. 代码简洁：实现相对简单，调试容易
  3. 常数因子小：实际运行时性能优秀
  4. 适合多查询：预处理一次，可以高效回答大量查询
  5. 支持任意结合律运算：不仅限于最值，还可用于GCD、AND、OR等

适用场景：

  • 静态数组，不修改
  • 大量区间查询
  • 查询区间是独立的
  • 需要快速查询响应

线段树优势：

  1. 支持动态修改：可以单点更新和区间更新
  2. 灵活性高：支持多种操作和懒标记
  3. 空间效率相对高：通常需要空间
  4. 适用范围广：支持更复杂的问题

适用场景：

  • 需要频繁修改数组
  • 需要区间更新操作
  • 需要维护复杂的信息
  • 动态变化的数据

选择建议：

|| 特性 | ST表 | 线段树 |
||------|------|--------|
|| 查询复杂度 | | |
|| 更新复杂度 | 不支持 | |
|| 空间复杂度 | | |
|| 适用性 | 静态查询 | 动态更新 |

返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

6. 练习题推荐

6.1 基础练习题

  1. [CSES 1649] Minimum Queries I

    • 难度：★★☆☆☆
    • 描述：使用ST表解决区间最小值查询
    • 知识点：ST表基础应用

  2. [CSES 1650] Maximum Queries I

    • 难度：★★☆☆☆
    • 描述：使用ST表解决区间最大值查询
    • 知识点：ST表基础应用

  3. [CSES 1143] Hotel Queries

    • 难度：★★★☆☆
    • 描述：结合ST表处理区间查询
    • 知识点：ST表与二分查找
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

6.2 中级练习题

  1. [CSES 1651] Range Update Queries

    • 难度：★★★☆☆
    • 描述：使用ST表处理区间查询问题
    • 知识点：ST表与差分

  2. [Codeforces 1516D] Cut

    • 难度：★★★★☆
    • 描述：使用倍增法处理区间GCD问题
    • 知识点：ST表、数论与二分查找结合

  3. [Codeforces 1314D] Minimum Path

    • 难度：★★★★☆
    • 描述：使用ST表解决路径最值问题
    • 知识点：ST表与动态规划
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

7. 总结

7.1 总结

ST表的核心要点：

  • 基本思想：

    • 基于倍增思想预处理
    • 预处理所有2^j长度的区间
    • 查询时分解为两个重叠区间

  • 关键技巧：

    • 动态规划预处理
    • log2数组预计算
    • 区间重叠保证覆盖
    • 支持任意结合律运算

  • 常见应用：

    • 区间最值查询(RMQ)
    • 区间GCD查询
    • 静态数组的快速查询
    • 大量查询场景

实践建议：

  1. 编码前：

    • 确认问题是否适合用ST表
    • 检查数组是否需要动态修改
    • 确认查询次数是否足够多

  2. 编码时：

    • 正确预计算log2数组
    • 注意动态规划递推关系
    • 处理好边界条件
    • 注意空间复杂度

  3. 调试时：

    • 验证预处理是否正确
    • 检查区间分解逻辑
    • 测试特殊输入
    • 确认结果正确性
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心

7.2 进阶方向

ST表的扩展：

  1. 持久化ST表：

    • 支持历史版本查询
    • 结合可持久化技术

  2. 动态ST表：

    • 支持在线更新
    • 维护ST表的高效更新

  3. ST表与其他算法结合：

    • ST表 + 二分查找
    • ST表 + 动态规划
    • ST表 + 贪心算法

  4. 高级应用：

    • 2D-ST表（二维ST表）
    • 稀疏表的其他变种
    • 在实际竞赛中的应用

实际应用中的注意事项：

  1. 在使用ST表之前，先考虑：

    • 数组是否需要动态修改
    • 查询次数是否足够多
    • 预处理开销是否值得

  2. 优化建议：

    • 位运算优化幂次计算
    • 优化内存布局
    • 考虑空间优化
    • 结合问题特性优化

  3. 记住：

    • ST表是倍增思想的重要应用
    • 理解区间分解原理是关键
    • 实践是掌握ST表的最佳途径
    • ST表与线段树各有优劣
返回目录 信息学 C++倍增法基础——ST表 魅客科创中心
C++倍增法基础——ST表

#c

演讲者备注不会在演示模式中显示给观众，仅供演讲者参考。 每个关键页面都添加了备注，帮助演讲者更好地讲解内容。

封面页： - 欢迎学生，简要介绍本次课程的主题和目标 - 强调ST表是倍增法的重要应用，在区间查询问题中非常关键 - 可以简单提及本课程将重点讲解ST表的原理、实现和应用

目录页： - 简要介绍本次讲座的结构和内容安排 - 可以提及讲座的逻辑流程：从RMQ问题到ST表原理，再到详细推导和应用 - 强调我们将通过多个例子来深入理解ST表的应用 - 提醒学生关注每个部分之间的联系，以及如何将理论应用到实践中

转场页： - 这是一个简单的转场页，用于引入RMQ问题概述部分 - 可以简单提及RMQ问题是区间查询中的经典问题

转场页： - 引入ST表原理与推导部分 - 可以简单提及理解原理有助于更好地实现ST表

转场页： - 引入ST表代码实现部分 - 可以简单提及掌握这些代码模板有助于快速实现ST表

转场页： - 引入ST表应用实例部分 - 可以简单提及我们将通过几个经典例子来深入理解ST表的应用