静态区间和与前缀和：从O(nm)暴力到O(1)查询的算法思维

咱们直接进入正题。今天聊一个 OI/ACM 入门绕不开、在牛客网每日一题里出镜率极高的模板题——静态区间和也就是前缀和。我当年刚刷题的时候看到这类题第一反应是“这有什么难的for 循环加一下不就完了”直到数据范围从 n100 变成 n10^6、查询次数从 1 次变成 m10^5 次才发现暴力累加的时间复杂度能把自己 T 到怀疑人生。这篇文章我就结合牛客上的模板题把前缀和从原理、推导到代码模板和变形题一次性讲透帮你把这块硬骨头啃下来。这篇内容适合三类人刚接触算法竞赛、想搞懂前缀和本质的新手已经会写模板但总在二维前缀和、边界下标上出 bug 的进阶选手以及准备刷牛客每日一题、想要一份可以直接照抄的 C/Python 模板的老哥。我会先讲清楚“静态”到底是什么意思再带你从暴力推导到 O(1) 查询的完整思路然后给代码模板最后聊聊那些看起来像前缀和、实际上得用哈希或树状数组的进阶题帮你建立一套完整的区间和解题直觉。1. 为什么“静态”两个字决定了算法选型1.1 先从一道标准模板题说起牛客网这类 OJ 上有道经典的入门模板题题面通常长这样给你一个长度为 n 的整数数组 a接下来有 m 次查询每次给一个区间 [l, r]要你输出这个区间内所有数字的和。n 和 m 的范围一开始给的是 10^5后来加强版能到 10^6 甚至 10^7。题目名字里有“静态”两个字很多人没注意但其实这两个字才是整个题目最关键的信息。所谓静态是指数组 a 在完成输入之后整个查询过程中不会被修改。也就是说没有“把某个位置的值改成新值”这种操作只有“求某段区间的和”这种只读操作。这个约束直接决定了我们用什么样的数据结构去解题。很多新手会把静态区间和题跟线段树、树状数组混在一起觉得“区间求和嘛线段树也能做用哪个都行”。这话在静态场景下没错但效率差远了。线段树单次查询是 O(log n)前缀和单次查询是 O(1)当 m 到 10^6 这个量级时前缀和跑完只需要几毫秒线段树可能要跑好几百毫秒差距是非常明显的。1.2 暴力解法的时间瓶颈到底在哪如果不用前缀和最朴素的做法是对于每次查询 [l, r]写一个循环从下标 l 累加到 r。这样做单次查询最坏要遍历完整段区间也就是 O(n)m 次查询就是 O(nm)。当 nm10^5那就是 10^10 次加法运算——普通 OJ 一秒能跑大约 10^8 到 10^9 条简单指令10^10 次加法大概要几十秒。这题基本就 TLE 定了。更关键的是暴力做法浪费了一个重要信息相邻两次查询之间数组本身没变。假设第一次查 [1, 5]第二次查 [1, 6]暴力做法会把前五个数再加一遍。可前五个数的和在第一次查询时其实已经算过了为什么不把它存下来直接复用前缀和的思想正是从这里长出来的——用空间换时间把重复计算变成一次预处理。1.3 前缀和本质上是一种“预计算”前缀和的英文是 prefix sum核心思想极其简单开一个额外的数组 sumsum[i] 表示原数组从第一个元素加到第 i 个元素的总和。因为“静态”所以 sum 这个辅助数组只要预处理一次之后所有查询都直接查表不需要再回头扫原数组。打个比方这就像你在一家餐厅点菜。暴力做法是每次点菜都去后厨从头开始炒前缀和的做法是后厨提前把所有菜的半成品都备好你点菜时只需要把对应半成品热一下端出来。静态场景下“备菜”这个工作只做一次收益非常大但如果是动态场景菜会临时换那备好的半成品可能过期就得换树状数组或线段树这类能动态更新的数据结构了。所以“静态”这两个字直接决定了前缀和是这个场景下的最优解。2. 前缀和数组的构建与查询公式推导2.1 O(n) 预处理递推式 sum[i] sum[i-1] a[i]假设原数组用 a[1] 到 a[n] 存储注意这里的下标我从 1 开始。为什么从 1 开始而不是 0这个我后文专门讲你先记住结论前缀和写题时下标从 1 开始能让代码简洁很多也能避免一堆边界 bug。定义前缀和数组 sum长度同样为 n1sum[0] 0。对于 i 从 1 到 n有sum[i] sum[i-1] a[i]这个递推式怎么理解sum[i] 是“前 i 个元素的和”sum[i-1] 是“前 i-1 个元素的和”两者之间只差一个 a[i]所以把它们加起来就行。这一步的复杂度是 O(n)只要扫描一遍原数组就能完成。这里有一个初学者特别容易忽略的细节sum[i] 这个数组存的是“前缀和”而不是“区间和”。它表示从数组头部到位置 i 的累计和更像一个“里程表”。我们要算任意区间的和还得再做一次减法。2.2 O(1) 查询区间 [l, r] 的和 sum[r] - sum[l-1]这个公式是整个前缀和的灵魂。推导过程很简单sum[r] 表示前 r 个元素的和sum[l-1] 表示前 l-1 个元素的和。前者比后者多的部分恰好就是从第 l 个元素到第 r 个元素这段也就是我们要的 [l, r] 区间和。所以区间和 [l, r] sum[r] - sum[l-1]看个具体例子。数组 a [3, 1, 4, 1, 5]前缀和数组是 sum [0, 3, 4, 8, 9, 14]。要查询 [2, 4]暴力是 1416用公式 sum[4]-sum[1]9-36完全一致。一次减法就能出结果跟区间长度完全无关这就是 O(1) 查询的来源。2.3 下标从 1 开始到底赢在哪里很多学 C/C 的同学习惯了数组下标从 0 开始写前缀和时也顺手下标 0结果每次查 [l, r] 都要在公式里纠结到底是 sum[r1]-sum[l]还是 sum[r]-sum[l-1]还是 sum[r]-sum[l-1] 再减个啥很容易乱。我个人强烈建议写前缀和时读入数据从 a[1] 开始存a[0] 空着不用前缀和数组 sum[0] 初始化为 0。这样一来查询 [l, r] 永远是干净的 sum[r] - sum[l-1]不用做任何下标偏移。l 如果等于 1那 sum[l-1] 就是 sum[0]0语义依然正确不会访问越界。下标从 0 开始也不是不能写统一用 sum[i] 表示“前 i 个元素的和”不包含 a[i]那么查询 [l, r] 就是 sum[r1]-sum[l]。这两种写法都行但问题是网上题解、牛客讨论区、模板题的标准答案绝大多数都用下标 1 那套。你如果跟主流保持一致后期看题解、对拍、抄模板都会顺畅很多。别在这种地方特立独行没必要。2.4 数据范围与溢出问题别用 int 存前缀和前缀和模板有个非常经典的天坑int 溢出。假设 n10^5a[i] 最大是 10^9那单个元素 int 能存下但前缀和 sum[n] 最大可以达到 10^14早就超出 int 的范围大概 2.1×10^9。所以前缀和数组一律用 long longC或 int64Go或 Python 直接不用管自动大整数。我见过太多新手写了 int sum[N]样例全过提交上去大数据直接 WA 或者显示奇怪的负数排查半天最后发现是溢出。这类模板题sum 数组无脑开 long long不会吃亏。3. 可直接照抄的 C 与 Python 模板代码3.1 C 标准模板快读 前缀和 查询下面这份代码是我每次写前缀和都会直接调用的标准模板注释写得很详细牛客上绝大多数静态区间和模板题都能直接用#include bits/stdc.h using namespace std; const int MAXN 1e6 5; long long a[MAXN], sum[MAXN]; // 快读处理大规模输入避免 cin 被卡 inline int read() { int x 0, f 1; char ch getchar(); while (ch 0 || ch 9) { if (ch -) f -1; ch getchar(); } while (ch 0 ch 9) { x x * 10 ch - 0; ch getchar(); } return x * f; } int main() { int n read(), m read(); for (int i 1; i n; i) { a[i] read(); sum[i] sum[i-1] a[i]; // 一边读一边构建前缀和省一次循环 } while (m--) { int l read(), r read(); printf(%lld\n, sum[r] - sum[l-1]); } return 0; }这段代码有几个细节值得展开说说。第一我一边读入一边构建前缀和输入 a[i] 的同时就直接累加到 sum[i]不用开完数组之后再单独跑一遍 for 循环。这不算什么优化但写起来更紧凑而且少了一次 O(n) 的遍历。第二cin 在大数据量下要先取消同步std::ios::sync_with_stdio(false)否则很容易被卡。如果你不想写快读至少加上这行。第三输出用 printf 而不是 cout同样是为了效率。3.2 Python 模板用 itertools.accumulate 一行构建Python 写前缀和最大的优势是代码超短而且没有整数溢出问题。但 Python 本身跑得慢牛客上如果 n 和 m 都到 10^6Python 可能会比较悬需要优化输入。我常用的模板是import sys from itertools import accumulate input sys.stdin.readline n, m map(int, input().split()) a list(map(int, input().split())) # 在头部补一个 0让下标对齐到 1 a [0] a sum_arr list(accumulate(a)) # 默认从第一个元素开始累加 res [] for _ in range(m): l, r map(int, input().split()) res.append(str(sum_arr[r] - sum_arr[l - 1])) sys.stdout.write(\n.join(res))这里用 itertools.accumulate 直接生成前缀和数组比自己写 for 循环要快不少是 CPython 底层的 C 实现。注意 accumulate 返回的是迭代器得 list 一下。a 补一个 0 是为了让 sum_arr[1] 对应到原数组第一个元素这样查询公式跟 C 版完全一致。如果遇到 10^6 级别的输入Python 读入也要小心map(int, input().split()) 处理 10 万个数没问题但如果一行有 100 万个数建议改用 sys.stdin.buffer.read() 一次性读入再 split速度会好一些。不过这是另一个话题了跟前缀和关系不大这里不展开。3.3 牛客输入输出格式的隐藏坑牛客的机试题有个特点很多模板题的数据不会保证 l r但多半会保证 1 l r n。也有少部分不保证需要你自己 if 交换一下。我建议无论题目有没有说都在查询前加一句 if (l r) swap(l, r); 或者 Python 里 l, r sorted([l, r])。多写这一行不亏万一题目数据不按套路出牌你就躲过一个 WA。还有一个小坑前缀和数组不要开成局部变量尤其是以 long long sum[100005] 这种方式写在 main 函数里面时栈内存不一定够用容易爆栈。最稳妥的写法是全局数组或者用 vector sum(n1) 动态分配。牛客的栈空间一般给得不大全局数组最安全。4. 二维前缀和从一维到矩阵的容斥原理4.1 矩形区间和问题的背景静态区间和模板题从一维数组扩展到二维之后就变成给你一个 n×m 的矩阵接下来 q 次查询每次给两个对角点 (x1, y1) 和 (x2, y2)求这个子矩形内所有元素的和。这类题也是前缀和模板里非常经典的存在牛客上经常出现。有人想类比一维的做法分别对行和列做前缀和然后查询的时候行减一下、列减一下——这个直觉方向是对的但具体公式需要仔细推导因为二维的“减法”涉及一个非常经典的容斥原理。4.2 二维前缀和数组的构建公式设二维前缀和数组为 pre[i][j]表示从矩阵左上角 (1,1) 到 (i,j) 这一整块矩形区域的和。构建时的递推公式是pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i][j]这个公式怎么理解pre[i-1][j] 包含了上方整块pre[i][j-1] 包含了左方整块。两者相加时左上角那块 pre[i-1][j-1] 被算了两次所以要减去一次。最后再加上当前格子 a[i][j]得到完整矩形和。跟你计算两个圆环总面积时的容斥原理一样A ∪ B A B - A ∩ B。4.3 查询公式三个减法一个加法构建好 pre 之后查询子矩形 (x1, y1) 到 (x2, y2) 的和公式是ans pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]推导思路跟构建公式完全对称pre[x2][y2] 是整个大矩形减去上方多出的部分 pre[x1-1][y2]再减去左边多出的部分 pre[x2][y1-1]但左上角那块 pre[x1-1][y1-1] 被多减了一次所以要加回来。你把这个画在坐标纸上用阴影图圈一下一眼就明白了。这里最容易犯的错是把 x1-1 写成 x1把 y1-1 写成 y1。我查了很多次 WA 之后发现问题就出在这个偏移上。建议你写完代码之后小数据手动模拟一遍或者直接用暴力程序随机对拍。4.4 二维模板代码C#include bits/stdc.h using namespace std; const int MAXN 1005; long long a[MAXN][MAXN], pre[MAXN][MAXN]; int main() { int n, m, q; scanf(%d%d%d, n, m, q); for (int i 1; i n; i) { for (int j 1; j m; j) { scanf(%lld, a[i][j]); pre[i][j] pre[i-1][j] pre[i][j-1] - pre[i-1][j-1] a[i][j]; } } while (q--) { int x1, y1, x2, y2; scanf(%d%d%d%d, x1, y1, x2, y2); long long ans pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] pre[x1-1][y1-1]; printf(%lld\n, ans); } return 0; }二维前缀和的构建和查询都是 O(1)预处理是 O(nm)整体复杂度对 10^3 级别的矩阵绰绰有余。如果你是做图像处理或者矩阵统计的这个模板可以直接改造成任意矩形范围内的求和累加器非常实用。5. 从前缀和衍生出去的三大经典变形5.1 差分前缀和的逆运算刷牛客每日一题时你大概率会遇到另一种模板题对一个数组做 m 次区间修改比如把 [l, r] 内每个数都加上某个值最后输出所有修改完成后的数组。这个题的思路叫差分跟前缀和是一对互逆操作。差分数组 d 的定义是这样的d[i] a[i] - a[i-1]对于 i 从 1 到 na[0] 视为 0。对 d 做前缀和就能还原出 a。区间修改 [l, r] 加 val 的操作等价于 d[l] val 且 d[r1] - val。为什么因为差分数组第 i 个位置记录的是“a[i] 相对前一个元素的变化量”区间内所有元素统一加 val变化量只在边界处改变。这个我建议你跟前缀和放在一起学因为理解前缀和之后学差分大概十分钟就能上手而它俩在很多题目中是配合使用的比如“多次区间修改 多次区间查询”的问题就要用差分配合前缀和一起做。前缀和本身是静态的差分则支持“静态的修改”算是往动态方向迈了一小步。5.2 前缀和 哈希表子数组和等于 K 的个数有一道非常经典的 LeetCode / 牛客题给你一个数组问有多少个子数组的和等于 k。暴力枚举所有子数组需要 O(n^2)但用前缀和可以把问题转化得非常优雅。设 sum[i] 表示前缀和那么子数组 [j1, i] 的和就是 sum[i] - sum[j]。我们要找 sum[i] - sum[j] k也就是 sum[j] sum[i] - k。于是遍历到 i 时只需查一下“之前出现过多少次 sum[i] - k”这个前缀和值并把当前 sum[i] 出现的次数加一。这个过程用哈希表维护前缀和频次整体复杂度降到 O(n)。这是前缀和一个非常漂亮的进阶应用也是牛客每日一题里经常出的“脑筋急转弯”型题目。很多新手看到题第一反应是滑动窗口但滑动窗口依赖单调性这题数组可能有负数滑动窗口是错的必须前缀和 哈希。5.3 前缀和最小值与最大子段和另一个跟前缀和强相关的经典问题是最大子段和。你可能会说这不是有 Kadane 算法吗是的但 Kadane 只是 O(n) 的另一种实现它的本质也可以用前缀和来描述枚举每一个位置作为子段右端点那么以 i 结尾的最大连续段和就是 sum[i] 减去前面最小的 sum[j]j i。这样只需要一边遍历一边维护“已出现前缀和的最小值”就能算出全局最大子段和。这个视角的好处是如果你需要支持“查询区间最大子段和”就能把问题推广到线段树可维护的形式。虽然线段树内容超出了今天的模板范围但理解前缀和是这条路的地基对你之后进阶非常有帮助。5.4 静态区间和的进阶何时升级到树状数组/线段树前缀和在静态场景下是最优解但它有个天然的局限不支持动态修改。如果题目变成“查询区间和 单点修改某个值”前缀和预处理完之后修改一个位置需要更新其后所有前缀和最坏 O(n)完全不可接受。这时就该换用树状数组或者线段树它们单点更新和区间查询都是 O(log n)。所以我的建议是凡是看到“静态区间和”“求区间和、无修改”“多次查询一个只读数组”直接无脑写前缀和看到“单点修改 区间查询”想树状数组看到“区间修改 区间查询”想线段树或树状数组 差分。前期把这三者的边界画清楚比盲目刷一堆题更管用。6. 牛客每日一题实测我的刷题顺序与调试心得6.1 推荐刷题路径如果你是想通过牛客的 tracker 系统刷前缀和这个模板我建议按这个顺序来先找一维前缀和的裸模板题把代码敲一遍过了就算入门然后找二维前缀和模板题重点体会容斥公式之后再找“前缀和 哈希”的题体会如何从裸模板抽象出数学关系最后再挑战前缀和与其他数据结构的综合题。每一步都确认自己理解了原理再进入下一层不要贪快。我自己当年刷题时有个习惯每道模板题至少用三种方式写一遍——第一遍照着思路写第二遍只看题解代码尝试理解别人为什么这样写第三遍合上书从头默写。三遍下来这套模板基本就成了肌肉记忆。6.2 常见 Bug 检查清单写前缀和最常见的坑我列一个清单你可以直接拿来自查前缀和数组是否开了 long longint 溢出会 WAl-1 是否写成了 l查询公式下标偏移错位数组是否从下标 1 开始如果从 0 开始是否统一了偏移一维前缀和排序后查询公式是否是 sum[r] - sum[l-1]二维前缀和的容斥公式是否多减了一次左上角读入优化是否到位大数据 cin 不取消同步会 TLE快读函数是否处理了负数输入的情况这 7 条几乎覆盖了我在牛客刷前缀和模板题时 90% 的提交错误。大多数时候不是思路错了而是这些细节上的问题。6.3 我实测的一些性能数据拿我本地环境Cn 10^6m 10^6 随机区间查询测试过暴力累加大概需要十几秒跑不完前缀和预处理加全部查询总运行时间大概 0.2 秒左右。这个差距直观到不需要多解释。Python 的话同样是 10^6 级别用 sys.stdin.buffer 读入 accumulate 构建总耗时大约在 1.5 秒到 2 秒有些牛客题会卡这零点几秒所以要是 Python 交了 TLE别急着怀疑算法先优化一下输入输出。二维的情况更敏感pre 数组如果用 int很容易在 nm1000、a[i][j]10^9 时溢出到负数。我踩过一次当时排查了很久最后把 int 全换 long long直接 AC。这个教训我一直记得。6.4 关于模板命名的一个小插曲有段时间我在看别人博客里的 C 模板时总看到评论区有人报错“类模板名称不能重复”这是因为博主写代码时用了 template 给某个类起了名字又在全局定义了几个变量名称冲突。这是我见过最多的非算法本身、但又影响刷题心情的报错。如果你也遇到这类问题最简单粗暴的办法是把模板参数名统一改成 T 或 U避免跟变量名、类型名撞车。这类语法坑比较碎但提前知道能省不少 Debug 时间。7. 我个人的一点经验前缀和不仅是模板更是“思维杠杆”很多人刷了十几道前缀和模板题之后会产生一种“这太简单了没啥含金量”的感觉转而去追那些酷炫的数据结构。但以我做算法题和带新人的经验看前缀和恰恰是性价比最高的知识点之一因为它帮你在“见题拆题”的思维层面建立了一种能力把重复计算变成预计算把区间问题变成端点问题。比如你在处理字符串的哈希匹配时会发现“字符串哈希”本质上也是一种前缀和——每个位置的权重累加然后用减法提取任意子串的哈希值。再比如统计数组中的逆序对、前缀最大值、前缀最小值这些全是同一个思维框架的延伸。区别只是前缀和存的是数值累计哈希存的是字符映射前缀最大存的是 max 的递推。所以我的建议是别只把前缀和当成一道需要 AC 的模板题而是当成一块思想跳板。每当你遇到一个场景需要反复查询一个“静态数组”的某种累积信息都可以停下来想一想能不能用 O(1) 的查询代价去换一个 O(n) 的预处理代价想通了这一层你以后学树状数组、线段树、莫队都会觉得亲切很多因为它们也都是在干同样的事情——用空间换时间无非是支持的修改程度不同。最后分享一个小技巧如果你自己刷牛客 tracker可以给每一类模板题建一个笔记把自己踩过的坑写在代码注释的最前面。我自己的前缀和代码开头的注释就写着“数组从 1 开始sum 用 long long查询公式 sum[r]-sum[l-1]”。刷题多了你会发现真正让你在赛场上省时间的不是临时推导公式而是这些已经刻进肌肉记忆的细节。把基础模板练成直觉你才能有余力去应对那些真正拉分的中等题。