# ST表（Sparse Table）教学设计

wflengxuenong · 2025-02-08 08:08:27 · 个人记录

一、引入：区间最值问题

问题场景：给定长度为n的静态数组，q次询问区间[l, r]的最大值/最小值
暴力解法：每次遍历区间 → O(nq)
优化需求：需要O(nlogn)预处理 + O(1)查询的算法

二、ST表核心原理

1. 核心思想

• 预处理：存储所有长度为2^j的区间最值
• 查询：将任意区间分解为两个预处理的区间

2. 数学基础

可重复贡献性质：
max(a,b,c) = max( max(a,b), max(b,c) )

3. 关键操作

• 预处理：

  st[i][j] = max(st[i][j-1], st[i+(1<<(j-1))][j-1])

• 查询：

  int k = log2(r-l+1);
  return max(st[l][k], st[r-(1<<k)+1][k]);

三、算法实现模板

int st[MAXN][21], Log2[MAXN];

void init() {
    Log2[1] = 0;
    for(int i=2;i<=n;++i) 
        Log2[i] = Log2[i/2]+1;

    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]);
}

int query(int l, int r) {
    int k = Log2[r-l+1];
    return max(st[l][k], st[r-(1<<k)+1][k]);
}

四、复杂度分析

• 预处理：O(nlogn)
• 单次查询：O(1)
• 空间：O(nlogn)

五、经典例题精讲

例题1：洛谷P3865 【模板】ST表

题目：静态区间最大值
代码要点：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int st[MAXN][21], Log2[MAXN];

int main(){
    int n,m; scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",&st[i][0]);

    // 预处理Log2
    Log2[1]=0;
    for(int i=2;i<=n;++i) Log2[i]=Log2[i/2]+1;

    // 构建ST表
    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]);

    // 处理查询
    while(m--){
        int l,r; scanf("%d%d",&l,&r);
        int k=Log2[r-l+1];
        printf("%d\n",max(st[l][k],st[r-(1<<k)+1][k]));
    }
    return 0;
}

例题2：CF1547F Array Stabilization (GCD version)

题意：环形数组，求最小操作次数使所有元素相等
ST表应用：预处理区间GCD
关键代码：

int query_gcd(int l, int r) {
    int k = Log2[r-l+1];
    return gcd(st[l][k], st[r-(1<<k)+1][k]);
}

六、进阶练习题

七、常见问题总结

1. 区间长度处理：注意r-(1<<k)+1可能越界
2. log2优化：预处理Log2数组比库函数更快
3. 适用场景：仅限静态数据，动态更新需用线段树

八、扩展思考

1. 二维ST表：处理矩阵最值查询
2. 混合运算：结合GCD、位运算等性质
3. 离线处理：结合Mo's Algorithm优化多查询

通过本教程的学习，结合配套的例题代码和练习题，能够快速掌握ST表的核心原理与实战应用。建议完成所有例题后，尝试独立完成练习题，并参考官方题解进行优化。