st表全称稀疏表Sparse Table大多数人第一次听说它是在刷题时遇到“区间最大值/最小值”这类问题。它最吸引人的地方是预处理完之后每次查询只需要 O(1) 的时间而你用的核心思想就是标题里写的“倍增技巧”。这篇文章我会把 ST 表的原理、C 代码、容易踩的坑一次性讲清楚适合正在学数据结构或者被 RMQ区间最值查询类问题卡住的朋友。先说个前置结论ST 表只适合“数组内容固定不变、查询次数特别多”的静态场景。它不支持修改这点很重要很多新手忽略后拿着它强行处理动态数组结果越用越难受。本文默认你有基本 C 语法基础就算没听过倍增也没关系我会从最朴素的场景开始拆。1. 先搞懂ST表在解决什么问题从区间查询到可重复贡献1.1 一个连续查询的场景没有修改的数组才是ST表的主场假设你在维护一组传感器数据共有 100000 个点现在不停有人来问“从第 i 个点到第 j 个点之间最大值是多少”也就是说查询区间可能是 [3, 99999]也可能连续来几万次不同的区间。数组本身不会变只有查询在变。最笨的办法是每次查询都遍历一遍区间里的所有元素。单次查询最坏 O(n)一万次查询就是 O(nq)数据稍微大一点就完全跑不动。如果你这时候用线段树单次查询是 O(log n)已经不错了但当查询量达到千万级别时log n 带来的常数仍然扛不住。ST 表的做法就很取巧提前把“所有长度为 2 的幂次的子区间答案”全部算好查询时直接拼出答案单次 O(1)。这种“预处理多一点查询快一点”的思路本质上是一种空间换时间的取舍。你花的代价是 O(n log n) 的预处理时间和空间换来的是海量查询下理论最优的 O(1) 单次查询。1.2 什么叫“可重复贡献”max和sum的差别就在这ST 表不是所有区间查询都能做它有一个重要前提被查询的操作必须满足“可重复贡献”。这个词听起来抽象其实意思很好理解。拿最大值来说查询区间 [l, r] 的前一半 [l, mid] 的最大值是 max1后一半 [mid1, r] 的最大值是 max2那么整段的最大值就是 max(max1, max2)。哪怕这两个区间有一部分重叠只要拿 max 再合并一次结果依然正确。比如你求 [1, 5] 和 [3, 7] 两个区间各自的最大值再取 max得到的结果和求 [1, 7] 最大值一样吗不一定一样但如果这两个区间覆盖住了目标区间取重叠部分不会再把某个重复的元素算了两次产生副作用。max、min、gcd、lcm、按位与、按位或都满足这个性质。反过来求和 sum 就不行。两个区间一旦重叠重叠部分的元素会被加两遍结果必然是错的。这就是“可重复贡献”和“不可重复贡献”的区别。ST 表查询时之所以允许两个预处理区间有重叠正是因为 max 这种操作的重叠是无害的。1.3 对比前缀和、线段树为什么偏偏选ST表把几个常见方案放在一起看你会更清楚 ST 表的坐标在哪里方案预处理时间单次查询时间支持修改适用操作暴力遍历O(1)O(n)是任意前缀和O(n)O(1)否可逆操作如 sum、xor线段树O(n)O(log n)是任意可合并操作分块O(n)O(√n)是任意可合并操作ST表O(n log n)O(1)否可重复贡献操作前缀和能做 sum 和 xor是因为它靠逆运算减回去但 max/min 这种操作没有逆运算前缀和就无能为力。线段树很通用既能修改又能查询但单次 O(log n) 比 O(1) 还是慢一截。如果你的数据量很大且查询极多又不要求修改ST 表就是最优选择。2. 倍增思想拆解为什么ST表能做到O(1)查询2.1 倍增的本质按2的幂准备“答案台阶”“倍增”这两个字核心就是“每次都按 2 的倍数往上翻”。放在数组上就是提前记录每个位置 i 开始往后长度为 1、2、4、8……这些 2 的幂次方的区间答案。这样做的理由很巧妙任意一个区间 [l, r] 的长度 len r - l 1一定可以找到一个最大的 2 的幂次 k使得 2^k ≤ len。比如 len6 时2^24 就是不超过 6 的最大 2 的幂次。这时候我从左端点 l 取长度为 4 的区间从右端点 r 往左取长度为 4 的区间这两个长度为 4 的区间一定会把整个 [l, r] 完整覆盖住只是中间会有一部分重叠。因为是 max/min/gcd 这类可重复贡献操作重叠部分不影响最终答案。最简单的类比是查地图你要看一段长路的信息先找一张覆盖范围恰好的比例尺地图不用一次次放大缩小。ST 表相当于把很多种“比例尺”提前印好查询时直接取最合适的那一张。2.2 预处理递推式st[i][k]怎么由两个半段拼出来预处理的核心是二维数组 st[i][k]它表示“从下标 i 开始长度为 2^k 的区间的最值”。当 k0 时长度是 2^01所以 st[i][0] 就是原数组第 i 个元素本身这是递归的起点。当 k0 时长度为 2^k 的区间可以平均拆成两半前半段是 [i, i 2^(k-1) - 1]后半段是 [i 2^(k-1), i 2^k - 1]两半长度都是 2^(k-1)。于是递推式是st[i][k] max(st[i][k - 1], st[i (1 (k - 1))][k - 1]);理解这个式子的关键在于右半段的起点是 i 2^(k-1)而不是 i 1。很多人第一次写会把起点写错导致结果完全不对。整个预处理的过程就是从小到大枚举 k先用长度为 1 的区间推长度为 2 的区间再用长度为 2 的推长度为 4 的一层一层往上“翻倍”。2.3 查询为什么只要O(1)重叠区间合并的关键查询 [l, r] 时先算长度 len r - l 1设 k floor(log2(len))。然后答案就是ans max(st[l][k], st[r - (1 k) 1][k]);第一个区间从 l 开始长度 2^k覆盖 [l, l 2^k - 1]第二个区间到 r 结束长度 2^k覆盖 [r - 2^k 1, r]。因为 2^k ≤ len所以这两个区间加在一起一定覆盖了整个 [l, r]又因为 2^k 是“不超过 len 的最大 2 的幂次”所以 2^k 不会小到中间留下空隙也不会大到越界。两段必然有重叠也没关系这正是前面强调“可重复贡献”的原因。查询过程中没有任何循环只做了一次 max、一次左移、一次数组访问所以是妥妥的 O(1)。3. C完整实现预处理、查询与边界测试3.1 先造一张lg表把log变成O(1)查询查询区间长度对应的 k 时如果用 math 库里的 log2 函数每次调用都有浮点运算还有可能因为精度误差踩坑。更稳的做法是提前预处理一张 lg 数组lg[i] 表示不超过 i 的最大 2 的幂次对应的指数也就是 floor(log2(i))。vectorint lg(n 1); lg[1] 0; for (int i 2; i n; i) { lg[i] lg[i 1] 1; }这个递推为什么对因为 log2(2 * x) log2(x) 1所以 lg[i] 可以直接由 lg[i/2] 推出来。比如 lg[1]0lg[2]lg[1]11lg[3]lg[1]11lg[4]lg[2]12。写这种预处理数组的习惯非常重要它能让你在查询阶段完全避开浮点数。3.2 预处理主循环外层枚举k内层枚举i顺序不能反完整预处理代码长这样const int LOG 20; // 2^20 1048576覆盖 1e6 以内的数据 vectorvectorint st(n 1, vectorint(LOG)); for (int i 1; i n; i) { st[i][0] a[i]; } for (int k 1; (1 k) n; k) { for (int i 1; i (1 k) - 1 n; i) { st[i][k] max(st[i][k - 1], st[i (1 (k - 1))][k - 1]); } }这里最重要的一个细节是循环嵌套的顺序外层必须是 k内层必须是 i。因为 st[i][k] 依赖的是 st[i][k-1] 和 st[i 2^(k-1)][k-1]也就是“长度更短”的区间答案。你必须先把所有长度为 2^(k-1) 的区间算完才能算长度为 2^k 的区间。如果内层枚举 i、外层枚举 k右侧的 st[i 2^(k-1)][k-1] 大概率还没算到结果就是随机错误。后面我还会专门讲这个坑。内层循环结束条件 i (1 k) - 1 n 也很关键它保证当前区间的右端点不越界。很多人写的是 i (1 k) n少减了一个 1结果最后一个元素永远算不进去查询时边界处就会出错。3.3 查询函数与一组手动模拟数据查询封装成一个 lambda 或者普通函数auto query [](int l, int r) { int k lg[r - l 1]; return max(st[l][k], st[r - (1 k) 1][k]); };我拿一组数据手算验证一下。假设数组 a {3, 1, 4, 1, 5, 9, 2, 6, 5, 3}注意我在工程代码里习惯让下标从 1 开始所以 a[1]3a[2]1以此类推。先看查询 [1,4]。len4lg[4]2k2。st[1][2] 表示下标 1 开始长度为 4 的区间即 [1,4]对应值 3,1,4,1最大值是 4st[4-41][2]st[1][2] 还是 4。最终答案 4正确。再看 [2,7]。len6lg[6]2k2。st[2][2] 覆盖 [2,5]即 1,4,1,5最大值 5st[7-41][2]st[4][2] 覆盖 [4,7]即 1,5,9,2最大值 9。max(5,9)9正确。最后看 [5,10]。len6k2。st[5][2] 覆盖 [5,8]即 5,9,2,6最大值 9st[10-41][2]st[7][2] 覆盖 [7,10]即 2,6,5,3最大值 6。max(9,6)9正确。这种手算的过程建议你第一次学的时候多跑几组理解“两个重叠区间覆盖目标区间”到底是怎么发生的。4. ST表实战场景RMQ模板与可重复贡献的变形4.1 可直接提交的RMQ完整模板我把完整代码整理成一个模板本地测试时可以直接改数组大小和输入格式。#include bits/stdc.h using namespace std; const int N 100005; const int LOG 20; int a[N]; int st[N][LOG]; int lg[N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; for (int i 1; i n; i) { cin a[i]; } for (int i 1; i n; i) { lg[i] lg[i 1] 1; } lg[0] 0; for (int i 1; i n; i) { st[i][0] a[i]; } for (int k 1; (1 k) n; k) { for (int i 1; i (1 k) - 1 n; i) { st[i][k] max(st[i][k - 1], st[i (1 (k - 1))][k - 1]); } } while (q--) { int l, r; cin l r; int k lg[r - l 1]; int ans max(st[l][k], st[r - (1 k) 1][k]); cout ans \n; } return 0; }注意 lg 数组在 main 里初始化时lg[1] 会被算成 lg[0]1 1但我们要的 lg[1]0所以要么先单独赋 lg[1]0要么像我这样初始化后单独把 lg[0] 修正为 0。这个细节很多人会忽略导致长度 1 的区间查询直接用 k1直接访问 st[l][1]取到了长度 2 的区间边界处就错。一个更稳的写法是在读入前先循环初始化for (int i 2; i n; i) { lg[i] lg[i 1] 1; }这样 lg[1] 保持默认的 0不会出问题。两种都行关键是别让 lg[1] 被错误覆盖掉。4.2 把max换成gcd看ST表如何轻松扩展ST 表的另一个好处是只要 merge 操作满足可重复贡献你几乎不用改结构只需要把 max 换成别的函数。比如区间 gcd预处理就变成st[i][k] __gcd(st[i][k - 1], st[i (1 (k - 1))][k - 1]);查询也对应改成__gcd(st[l][k], st[r - (1 k) 1][k])。同样按位与、按位或、lcm 都可以这样做。这就让 ST 表成为一个“半通用”的数据结构核心骨架不动替换合并函数即可。不过要注意lcm 数值容易撑爆 int而且合并时要先除 gcd 再乘否则中间结果可能溢出。如果你要返回的答案类型是 long long那整个数组 st 都要改成 long long不能只改一个查询函数否则 tmp 就会被截断。4.3 什么样的题不能用ST表ST 表最致命的限制是不支持修改。只要题目里有“把某个位置的值改成 newVal”这种操作ST 表就不能用因为它需要重新预处理 O(n log n) 才能反映单点修改这比直接用线段树 O(log n) 慢太多了。另一个限制是可重复贡献。比如“区间和”就不能用 ST 表虽然可以改用线段树或前缀和。“区间最大值出现的位置”这类问题如果只存一个下标不能靠简单地 max 合并需要另外维护。凡是题目让你求“区间第 k 大”“区间众数”“区间和”这类不满足可重复贡献的查询ST 表都不是首选。还有空间限制。二维数组 st[n][LOG] 在 n1e6 时大约占 80MB某些评测机上可能直接致命。遇到这种情况可以换分块或者线段树。5. 常见问题与排查技巧实录踩过的坑一次性列给你5.1 循环顺序写反为什么结果时对时错这是我见过最多的问题也是我自己早年反复踩过的一个坑。有人写预处理时把循环写成for (int i 1; i n; i) { for (int k 1; i (1 k) - 1 n; k) { st[i][k] max(st[i][k - 1], st[i (1 (k - 1))][k - 1]); } }表面上看逻辑没毛病实际一测就会发现短区间偶尔正确长区间随机错。原因是当你计算 st[i][k] 时需要读 st[i 2^(k-1)][k-1]而这时 i 还没循环到那个较大的值st[i 2^(k-1)][k-1] 还是默认的 0 或者上一轮残留的数值。哪怕你后面再遇到它也来不及回头修正已经算错的结果了。排查这类问题的办法很简单对比暴力。写一个 O(n) 查询的暴力函数用随机数组、随机查询区间和 ST 表结果对拍。对拍一两次就能发现异常这时候再检查循环顺序基本一眼就能看到问题。5.2 0下标和1下标混用最常见的隐形地雷C 数组足够灵活你既可以从 0 开始也可以从 1 开始。最怕的是建表用一套下标查询用另一套中间边界逻辑全乱。如果都从 0 开始预处理内层循环的右边界判断要改成i (1 k) n因为最后元素下标是 n-1长度 2^k 的区间覆盖的是 [i, i 2^k - 1]所以保证 i 2^k - 1 ≤ n-1即 i (1k) ≤ n。查询时右区间的起点是 r - (1 k) 1这里 r 仍是 0 下标逻辑本身没问题但代码读者很容易混淆。我个人建议统一用 1 下标。这样预处理边界就是经典的i (1 k) - 1 n查询测试也好验证。唯一要注意的是读入数组时从 a[1] 开始数组开头留一个空位不用别把 a[0] 当成第一个有效元素。5.3 内存、类型与常数优化大数组下的生存指南先说数据范围。n 最大 100000 时log2(100000) 约等于 17LOG 取 20 足够。n 最大 1000000 时LOG 取 20 也够因为 2^20 1048576。如果 n 更大要相应增大 LOG否则数组访问越界查询结果完全不可预测。再说类型。所有答案类型必须保持统一。如果你求的是 int 范围内的 max/minint 就行但如果数据范围很大比如让你求区间乘积或者 gcd 的 lcm这时中间结果可能超 int我建议直接全局用 long long省得调试半天发现是类型溢出。st 数组的每个元素都要改不只是 merge 函数。最后说常数。查询语句里的1 k每次都会算而在海量查询场景下这几次移位运算就是额外开销。一个很常见的微优化是预处理时把每个 k 对应的区间长度存成数组len[k] (1 k)查询时直接用 len[k]既省去了移位运算代码也更清晰。虽然 O(1) 查询本身已经足够快但这类细节习惯能帮你写出更高效的程序。6. 倍增思想的扩展从ST表到树上LCA与更多场景6.1 树上倍增从st数组到LCAST 表只是倍增思想在数组上的一个应用。你一旦理解了“按 2 的幂跳步长”的套路再学树上倍增几乎不用花额外精力。树上倍增的核心是 up[u][k]从节点 u 向上走 2^k 步到达的祖先节点。递推式是 up[u][k] up[ up[u][k-1] ][k-1]意思是先跳 2^(k-1) 步到某个中间节点再从这个中间节点继续跳 2^(k-1) 步。这和 st[i][k] max(st[i][k-1], st[i 2^(k-1)][k-1]) 的“分两半拼起来”思路是完全一致的。最常见的用途是求两个节点的最近公共祖先LCA。先把两个节点深度对齐再按照二进制从大到小一起往上跳最后跳到目标位置。当年我先学 ST 表再学 LCA整个过程顺畅得惊人因为思维模型已经提前建立好了。6.2 二维ST表与更多变形二维矩阵的静态子矩阵最大值查询同样可以用倍增。平时比较常见的写法是 f[i][j][k] 表示以 (i,j) 为左上角、边长为 2^k 的正方形内最大值预处理时也是拆成四个小正方形查询时取四个重叠正方形的 max。代码会比一维版绕很多但读起来无非就是“预处理可重叠性区间的答案查询用四块拼”。类似地还可以做“区间按位与”“区间按位或”“区间 gcd”这些可重复贡献操作的静态 O(1) 查询。图像处理中固定窗口的极值计算、一些统计类算法里的静态打分表都可能用到二维版本。6.3 学习ST表的正确姿势与我的经验我写过不少数据结构但 ST 表是每次重新教人时都会推荐的入门倍增素材因为它的代码量刚刚好不会复杂到劝退又包含了“二进制拆步长”“空间换时间”“预处理顺序依赖”这些高频考点。我的个人练习建议很简单先不看任何模板自己凭理解写一遍 ST 表写完后用暴力函数对拍随机生成数组和区间反复验证最后把 max 换成 gcd 再跑一遍看看自己对“可重复贡献”的理解是否真的到位。对拍这一招真的能解决绝大多数调试问题比盯着代码看半天高效太多。如果你刚学完前缀和和线段树选一个下午专门把 ST 表从原理到代码完整走一遍绝对比你泛泛地看十篇博客有用。它就是那种“代码只有几十行但思维能复用很久”的典型代表。