滑动窗口最大值这道题很多人在初学算法时都刷过最常见的解法是单调队列一趟扫描搞定时间复杂度 O(n)。但如果你只是背了个单调队列模板往往会忽略一个同样经典甚至在更多 RMQ区间最值查询场景里更通用的工具ST 表Sparse Table。这篇指南我打算从零开始把 ST 表的原理、预处理、查询、模板代码和滑动窗口最大值的完整例题解析一次讲透顺便把我在实际写代码时踩过的坑和排查思路一起整理出来。不管你是刚学会数组和循环的新手还是准备面试需要系统补数据结构的老手跟着走一遍都能写出能跑的代码并且搞清楚它为什么这么写。先说明白一点滑动窗口最大值这道题标准最优解确实不是 ST 表而是单调队列。但这不妨碍我们认真学 ST 表因为它解决的是静态区间可重复贡献查询这一类问题滑动窗口最大值只是它的一个特例。学完它区间最小值、区间 GCD、区间按位与这些问题你会一通百通。1. 滑动窗口最大值的本质与解法选型1.1 问题到底在问什么暴力解法为什么不行题目描述很朴素给定一个长度为 n 的数组 a[1..n]以及一个固定大小的窗口 k窗口从左往右每次滑动一格要求输出每个窗口内的最大值。比如数组是 [1, 3, -1, -3, 5, 3, 6, 7]k 3那么第一个窗口 [1, 3, -1] 的最大值是 3第二个窗口 [3, -1, -3] 的最大值是 3依次类推一共要输出 n - k 1 个结果。最直观的做法是暴力每个窗口都扫一遍里面的 k 个元素取最大值。这个思路完全正确但复杂度是 O(nk)。假设 n 100000k 50000那就是 50 亿次比较在绝大多数在线评测系统上都会超时。问题难在哪里难在窗口每移动一次旧的元素离开新的元素进入窗口内部的最大值不是简单的继承关系——离开的元素恰好是最大值或者新进入的元素很大都会让结果突变。你没法像维护前缀和那样用一两个前缀值加减得出答案。前缀和之所以不行是因为它只支持可逆运算即区间和可以通过两个前缀和相减得到。但最大值这个运算是不可逆的你知道了 [1..r] 的最大值和 [1..l-1] 的最大值并不能推出 [l..r] 的最大值。这就逼着我们换一种数据结构来思考。1.2 五条主流路线为什么单独把 ST 表拎出来讲针对静态数组的区间最值查询业界常见的解法有这么几类我直接列个对比表解法预处理复杂度单次查询复杂度支持动态修改特点暴力扫描O(1)O(k)支持思路最简单只适合小数据单调队列O(n)均摊 O(1)支持滑动窗口滑动窗口场景的最优解优先队列堆O(n)O(log n)支持实现简单但要配合懒删除线段树O(n)O(log n)支持动态区间最值的通用解ST 表O(n log n)O(1)不支持静态 RMQ 查询速度无敌看到这张表你可能会问既然单调队列又快又简单为什么还要花一篇的篇幅学 ST 表原因有两个。第一ST 表的 O(1) 查询在大量离线查询场景下是碾压级的优势。比如你拿到一万个随机区间 [l, r]要求每个区间的最大值单调队列反而不好套ST 表预处理完之后每个查询就是一次常数级操作。第二ST 表背后的倍增思想是算法竞赛和高频面试里反复出现的基础思维线段树的区间合并、LCA 的倍增跳法全都和它同源。学一次 ST 表相当于同时预习了五六个进阶知识点。2. ST 表核心原理倍增与重叠覆盖2.1 预处理的是什么东西st[i][j] 到底存了什么ST 表的预处理思路用一句话概括就是把数组切成大量长度为 2 的幂的区间预先算出每个区间的最值查询时用两个已知区间拼出目标区间。具体定义是这样的st[i][j]表示从下标 i 开始、长度为 2^j 的区间即 [i, i 2^j - 1] 这个范围内的最大值。注意这里 j 不表示终点而是表示长度级别。比如 j 0 时st[i][0] 就是区间 [i, i] 的最大值也就是 a[i] 本身j 1 时st[i][1] 是 [i, i1] 两个元素的最大值j 2 时st[i][2] 是 [i, i3] 四个元素的最大值。你可以把它想象成一本阶梯书签第 0 层每个位置只管自己一个数第 1 层每两个数共用一个结果第 2 层每四个数共用一个结果。每一层的区间接力式翻倍。为什么偏偏选 2 的幂因为任何一个正整数都可以表示成若干个 2 的幂的和这保证了我们能用 O(log n) 个标准长度区间覆盖任意长度区间。ST 表在此基础上更进一步利用重叠无害的性质把 O(log n) 次合并压缩成了 O(1) 次具体机理在 2.3 节讲。2.2 状态转移方程为什么必须把 j 放在外层循环st[i][j] 的值不是凭空算出来的它从两个长度为 2^(j-1) 的子区间拼接而来。把 [i, i 2^j - 1] 从中间一分为二左半边[i, i 2^(j-1) - 1]对应 st[i][j-1]右半边[i 2^(j-1), i 2^j - 1]起点是 i 2^(j-1)长度仍是 2^(j-1)对应 st[i 2^(j-1)][j-1]所以状态转移方程是st[i][j] max(st[i][j-1], st[i 2^(j-1)][j-1])初始条件就是 st[i][0] a[i]。这段逻辑本身不难难的是实现时的循环顺序。请看这个依赖关系我们计算 st[i][j] 时依赖的是第 j-1 层的两个值。也就是说整张表必须一层一层地算——先把所有位置的 st[i][0] 填好再填所有 st[i][1]然后才是 st[i][2]。如果把 i 放在外层、j 放在内层那么算到 st[i][2] 时它依赖的 st[i 2][1] 可能还没被计算到结果就会错得莫名其妙。代码里的循环结构就应该是这样for (int j 1; (1 j) n; 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]); } }内层循环的上界i (1 j) - 1 n保证了我们不会越界访问数组。很多新手会漏掉这个条件或者写成i (1 j) n差一个 1 就是数组越界和答案错误的分界线务必看清楚。2.3 O(1) 查询的数学基础区间为什么允许重叠ST 表最妙的地方在于查询这个环节。给定任意查询区间 [l, r]我们记区间长度 len r - l 1然后取 k floor(log2(len))也就是小于等于 len 的最大 2 的幂所对应的指数。注意这里我们不需要把 len 拆成多个 2 的幂之和只需要用两个长度为 2^k 的区间第一个区间从 l 开始[l, l 2^k - 1]对应 st[l][k]第二个区间到 r 结束[r - 2^k 1, r]对应 st[r - 2^k 1][k]然后直接取这两个区间的最大值作为答案。为什么这样是对的关键在于 k 的取值保证了两个区间必然覆盖整个 [l, r]。因为 2^k len所以第二个区间的左端点 r - 2^k 1 l第一个区间和第二个区间要么刚好相邻要么相互重叠不会有空隙又因为 len 2^(k1)所以第二个区间的左端点不会越过第一个区间的右端点两个区间都不会超出 [l, r] 的边界。合在一起它们的并集正好完整覆盖住 [l, r]。那重叠的部分怎么办这里就要引出一个非常重要的概念ST 表只能处理可重复贡献问题。所谓可重复贡献是指这个运算满足结合律并且同一个元素被重复参与计算不影响最终结果。最大值就满足这一点max(x, x) x就算重叠区域被算了两次得出的最大值也不会变。最小值、最大公约数、按位与、按位或也都满足这个性质所以 ST 表统统能处理。但区间求和不满足——重叠区域被加两次结果就错了。这也是为什么 ST 表不能替代前缀和去算区间和两者适用的运算是两个不同的集合。3. 手写 ST 表模板从预处理到查询3.1 预处理细节lg 数组、二维数组大小、初始化顺序正式写代码之前要先准备一个辅助数组 lg[x]用来快速求出 floor(log2(x))。注意这里不能用 C 的 log2 函数直接算整数因为浮点误差在某些边界值上会翻车而且每次查询都调用 log2 会有不必要的常数开销。预处理 lg 数组的经典写法是lg[1] 0; for (int i 2; i n; i) { lg[i] lg[i / 2] 1; }为什么这样写因为 floor(log2(i)) 和 floor(log2(i/2)) 之间恰好差 1。你可以拿几个数验证lg[1] 0lg[2] lg[1] 1 1lg[3] lg[1] 1 1lg[4] lg[2] 1 2。完全正确。二维数组的列数 LOGN 取多大只要满足 2^LOGN n 就行。绝大多数情况下 n 不超过 10 万2^17 131072所以 17 足够如果 n 到了 100 万那就要取 20。稳妥做法是开一个常量const int LOGN 20;或者用(n).bit_length()C 里可以写成__lg(n) 1动态计算。内存方面n 10 万时st 数组是 100000 x 17 个 int大约 6.8MB完全无压力但 n 到 100 万时就是 80MB在内存受限的环境里就要小心了这种情况建议换单调队列或者分块。3.2 查询模板与边界思考查询函数的代码很短但每一处边界都值得掰扯int queryMax(int l, int r) { int len r - l 1; int j lg[len]; // 覆盖 len 的最大 2 的幂的指数 return max(st[l][j], st[r - (1 j) 1][j]); }r - (1 j) 1这个写法是最容易写错的地方很多人会漏掉最后的 1。我们推导一下第二个区间长度是 2^j终点是 r所以起点就是 r - 2^j 1。少一个 1起点就会往左偏一位查询结果可能来自窗口外的元素答案错误。另外这个查询模板适用于任何 [l, r]不需要管窗口大小是否正好是 2 的幂也不需要管两个子区间是否重叠——这正是 2.3 节讲的重叠无害带来的便利。3.3 模板的易错点速查我把这个模板常见的坑整理成了一个小表写代码之前对照一眼能省很多调试时间易错点错误写法正确做法后果预处理循环顺序i 在外层j 在内层j 在外层i 在内层依赖值未算出结果乱套内层循环上界i (1 j) ni (1 j) - 1 n数组越界或漏解第二个区间起点r - (1 j)r - (1 j) 1查询结果偏向左侧lg 数组初始化从 i1 开始lg[i]lg[i/2]1导致 lg[0] 参与保证 lg[1]0从 i2 开始lg 值偏大k 取错LOGN 过小固定 10满足 2^LOGN n高长度区间查询越界4. 例题全解析滑动窗口最大值的 ST 表解法4.1 题目描述与破题思路经典版题目是这样的输入第一行给出两个整数 n 和 k分别表示数组长度和窗口大小第二行给出 n 个整数。要求输出 n - k 1 个整数分别是每个窗口中的最大值。这道题在大量在线评测系统里都有收录也是很多公司面试题库里的常客大家应该不陌生。用 ST 表解这道题的破题思路其实非常直白窗口所有可能的位置也就是区间 [1, k]、[2, k1]、...、[n-k1, n]全都是事先确定的静态区间。这正好命中 ST 表的最佳场景——静态数组上的批量区间最值查询。我们只需要做一次 O(n log n) 的预处理然后对每个窗口执行一次 O(1) 的 queryMax就能把全部答案算出来。总复杂度 O(n log n n)虽然不如单调队列的 O(n)但在常规数据范围下完全够用而且代码的可推导性更强不太容易写出隐蔽 bug。4.2 C 完整实现与逐段讲解下面是一份可以直接提交的 C 代码我加了足够的注释#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOGN 17; // 2^17 131072 1e5 int n, k; int a[MAXN]; int st[MAXN][LOGN]; int lg[MAXN]; int queryMax(int l, int r) { int len r - l 1; int j lg[len]; return max(st[l][j], st[r - (1 j) 1][j]); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k; for (int i 1; i n; i) cin a[i]; // 1. 预处理 lg for (int i 2; i n; i) lg[i] lg[i / 2] 1; // 2. ST 表第 0 层 for (int i 1; i n; i) st[i][0] a[i]; // 3. 倍增递推j 在外层 for (int j 1; (1 j) n; 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]); } } // 4. 每个窗口一次查询 for (int i 1; i k - 1 n; i) { int ans queryMax(i, i k - 1); cout ans (i k - 1 n ? \n : ); } return 0; }这里有三处实现细节值得说明。第一数组下标统一从 1 开始这样窗口区间 [i, ik-1] 表达起来非常自然不容易出现差一错误。第二预处理的边界条件(1 j) n和i (1 j) - 1 n是配套的前者保证存在至少一个长度为 2^j 的合法区间后者保证当前这个具体区间不越界。第三查询循环里i k - 1 n用来控制换行这只是输出格式要求和算法本身无关。4.3 Python 实现参考如果平时主要用 Python 刷题下面是等价实现。Python 的二维列表写法以及 bit_length 的用法稍有不同我直接在代码里标注出来import sys def main(): data sys.stdin.buffer.read().split() n int(data[0]) k int(data[1]) a list(map(int, data[2:2 n])) # n.bit_length() 保证 2^LOG 能覆盖 n LOG n.bit_length() # st[i][j]从 i 开始长度 2^j 的最大值 st [[0] * LOG for _ in range(n)] for i in range(n): st[i][0] a[i] # j 外层和 C 同理 for j in range(1, LOG): step 1 (j - 1) limit n - (1 j) 1 for i in range(limit): st[i][j] max(st[i][j - 1], st[i step][j - 1]) # lg 数组 lg [0] * (n 1) for i in range(2, n 1): lg[i] lg[i 1] 1 ans [] for l in range(n - k 1): r l k - 1 length r - l 1 j lg[length] ans.append(str(max(st[l][j], st[r - (1 j) 1][j]))) sys.stdout.write( .join(ans)) if __name__ __main__: main()Python 版本注意两点一是n.bit_length()对于 n 100000 会返回 17正好覆盖到长度 2^16 65536 的预处理级别查询时 lg[len] 最大也是 16不会越界二是如果 n 1bit_length 返回 1内层 j 循环range(1, 1)直接不执行st 只有第 0 层查询依然正确。4.4 这题的标准答案为什么是单调队列我必须把话说透纯粹为了 AC 这道滑动窗口最大值题单调队列才是标准解法。它的核心思想是维护一个内部元素从队头到队尾单调递减的队列窗口滑动时新元素进队前先把队尾所有比它小的元素弹出再把队列头部超出窗口范围的元素弹出队头元素就是当前窗口的最大值。整个过程每个元素最多进队一次、出队一次总复杂度 O(n)代码也不长。那 ST 表的意义在哪里在于它把这道题从专门技巧提升到了通用模型。窗口大小固定且连续滑动用单调队列最舒服但如果查询窗口的位置是任意的甚至查询区间数量高达几十万个且相互之间没有任何滑动关系单调队列就尴尬了ST 表却能一视同仁地 O(1) 回答每个查询。我在实际做题中的体会是这两者不是替代关系而是互补关系。面试时如果能把两种方案都讲清楚并指出各自的适用边界比只背一个模板能拿到的印象分高得多。5. 常见问题与排查经验5.1 预处理循环顺序写反了现象是什么最经典的翻车现场就是把 i 放在外层、j 放在内层。错误代码长这样for (int i 1; i n; i) { for (int j 1; (1 j) n; j) { st[i][j] max(st[i][j - 1], st[i (1 (j - 1))][j - 1]); } }编译能通过小数据偶尔也能跑对但数据一大结果就错得离谱。原因就是计算 st[i][j] 的时候需要依赖 st[i 2^(j-1)][j-1]而内层循环从 j 从 1 开始变大的过程中那一列的更小 j 值只算到了当前的 i还没有算到更大的 i。换句话说你用一个还没填好的格子去更新另一个格子相当于站在半成品地基上盖楼。排查方法很简单随便挑一个长度 5 以上的小区间手算一遍正确结果对比输出立刻就能暴露问题。5.2 lg 数组求错的隐蔽场景lg 数组的经典错误是写出lg[i] lg[i - 1] (i (i - 1) 0)这个写法的本意是遇到 2 的幂就加一但位运算优先级容易踩坑而且边界判断麻烦。我强烈建议统一用lg[i] lg[i / 2] 1这个版本。另外注意lg[0] 在 C 全局数组里默认是 0但理论上 lg[0] 是没有意义的如果查询时错误地把长度为 0 的区间传进函数就会用到这个 0从而返回 st[l][0] 之类的错误结果。所以查询函数入口最好保证 len 1在滑动窗口场景里这天然满足。5.3 查询函数里那个 1 为什么老是被漏r - (1 j) 1里的 1 是差一错误的重灾区。我的记忆方法是区间 [l, r] 的长度是 r - l 1那么已知终点 r 和长度 len 时起点就是 r - len 1。这里 len 2^j所以起点 r - 2^j 1。你在草稿纸上推一次这个公式把它和长度公式里也有 1对应起来就不容易忘了。如果真的漏了症状也很典型窗口较大时查询结果会整体偏向左边而且越靠右的窗口偏差越大非常难一眼看出来。5.4 内存和常数的现实考量ST 表空间是 O(n log n)这个代价在 n 10 万时很轻松但 n 100 万时就到了 80MB 左右很多平台的默认内存限制会顶不住。我在实际处理超大数据时通常会先评估问题类型如果只是单次滑动窗口直接上单调队列如果是静态离线批量查询可以考虑基于分块的稀疏表Sparse Table on Blocks或者干脆用线段树。另外查询量非常大时ST 表的优势才会完全显现因为预处理和查询的常数都很小远优于线段树每次 O(log n) 的递归开销。5.5 一个很容易被忽略的定位问题ST 表不支持修改ST 表构建完成后数组里任何一个元素发生变化理论上所有覆盖它的区间都要重新计算相当于重新预处理一遍。所以它是彻底的静态数据结构。如果你的题目里有单点更新 区间查询这种动态操作请直接放弃 ST 表老实上线段树或树状数组。判断方法非常粗暴题目里出现修改更新字样ST 表就要打个问号出现静态离线只查询字样ST 表就是首选之一。5.6 我的一段调试心得初学 ST 表时我最常犯的错反而不是边界而是想当然地以为递推方向无关紧要。为了彻底搞懂 j 外层循环的必要性我在纸上给一个长度为 8 的数组完整手算了 st 表的前三层然后用错误的循环顺序又算了一遍。两版结果一对比墙面上的错误豁然开朗。我强烈建议你也这么做一次拿 [2, 1, 4, 5, 3, 8, 6, 7] 这样的数组手算 st[i][0]、st[i][1]、st[i][2]再照着这个手写过程对照你的代码所有抽象的原理都会具体化。6. 从滑动窗口到更广阔的 RMQ 世界6.1 可重复贡献问题全家桶前面反复强调可重复贡献这里总结一下 ST 表到底能处理哪些运算最大值、最小值、最大公约数GCD、最小公倍数LCM、按位与AND、按位或OR、按位异或XOR 其实不满足可重复贡献因为 x^x 0重叠会把贡献抵消所以要慎用。这些运算都有一个共同点它们都满足结合律并且同一元素参与多次计算不会改变结果。比如求一个区间所有数的 GCD重叠区域里的数被算了两次但不影响整个区间的 GCD但求区间和就不行重叠意味着重复相加。正因为如此ST 表的能力边界非常清晰它能一招通吃所有幂等结合运算的静态区间查询。你的知识库里只要有一个 ST 表模板等于同时掌握了六七个问题的通用解法。这也是为什么我始终认为即使知道单调队列是滑动窗口的最优解ST 表依然值得投入时间去学透。6.2 静态查询场景怎么选型根据自己的刷题经验我总结了一张简单的选型决策表场景特征推荐方案原因窗口固定、连续滑动单调队列O(n)无预处理负担静态数组、海量随机区间查询ST 表O(1) 查询预处理一次性摊薄需要单点更新线段树 / 树状数组ST 表无法承受频繁重建数据量极大、内存吃紧分块 预处理块内信息空间降级到 O(n)查询 O(sqrt(n))查询区间事先未知、动态在线线段树动态结构最稳定ST 表还有一类衍生用法值得一提在离线算法中配合其他思想使用。比如把原数组按某种规则排序后把查询区间按照右端点排序再用 ST 表辅助维护某些可合并信息这已经进入了更高阶的算法设计范畴。学有余力的读者可以把 ST 表理解为倍增思想的存储形态后面学 LCA 的树上倍增、后缀数组的 RMQ 辅助时你会发现全是老朋友。6.3 我给新手的学习路线建议如果这篇文章只能记住一句话我想是这句先暴力再 ST再单调队列。暴力让你理解问题本质ST 表让你掌握通用模型单调队列让你知道最优解如何诞生。按这个顺序学每一步的动机都非常清楚而不是一上来就背模板。具体来说拿到这类区间最值题先确认是否静态、是否离线、是否有修改再看查询数量和数据范围。遇到滑动窗口且 n 很大默认往单调队列想遇到静态数组加一堆随机区间查询往 ST 表想遇到动态更新往线段树想。选型这关过了题目已经解了一半。我最后再分享一个小技巧写 ST 表模板时把 queryMax 单独抽成一个函数并且在函数开头用 assert 保证 l 1 且 r n。调试阶段开着 assert提交前再关掉能帮你拦截掉绝大多数下标越界问题。这个习惯我从第一次手写 ST 表一直保留到现在省下来的调试时间难以估量。