引出今日主题静态区间和与前缀和2026年1月21日的牛客每日一题出的是一道非常经典的基础题——静态区间和解法对应的正是前缀和。如果你刚开始刷题看到“区间和”三个字可能会想不就是循环加一遍吗但为什么每次题目一拿到“区间查询”场景暴力循环往往就超时前缀和能解决的场景远不止“求一段和”这么简单它是一连串高级算法差分、二维前缀和、离线查询、配合哈希的变种题的地基。这篇文章我会拆透这道题——从暴力做法讲起再到一维前缀和的数学原理、下标陷阱、常见踩坑点最后推到二维版本让你看完之后不只是“AC了这题”而是彻底理解这类题的所有套路。这篇文章适合的人群刚开始刷题的大学生、准备面试的求职者、想系统补习基础算法的开发者。如果你是零基础也不用担心我会从数组下标和累加逻辑开始讲所有代码都会给出完整样例。1. 静态区间和到底是个什么问题1.1 题目背后的本质多次查询性能关键简单说静态区间和就是给你一个数组之后有一大堆查询每个查询问“从第 L 个位置到第 R 个位置或下标从 L 到 R的元素加起来是多少”。关键在于“静态”两个字——数组从头到尾不会被修改只有查询动作。听起来很简单但奥妙在于“一堆查询”。如果数组长度是 n查询次数是 q最坏情况下每个查询都扫描整个数组总复杂度就是 O(nq)。当 n 和 q 都取到 10^5 甚至 10^6 量级时暴力循环就完全扛不住了这是比赛中非常经典的超时模型。有一类改进思路是“预处理”既然数组是静态的那我可以花一些时间提前准备好一个辅助结构让每次查询变得极快。前缀和正是这种“用空间换时间”思路的极致体现——一次 O(n) 的预处理换来每次查询 O(1) 的响应。1.2 从暴力循环到直觉飞跃你第一次写区间和很可能是这样实现的// 暴力解法 int query(int L, int R) { int sum 0; for (int i L; i R; i) { sum arr[i]; } return sum; }这段代码思路没问题问题出在多次调用时的累计开销上。每次查询都是一次全新遍历前面算过的结果完全没有留下来复用。想象你在一本日历上快速查找一个月里某几天的累计开销。如果你每天记一笔账那么问“1号到10号总共多少钱”你会从1号加到10号。但如果问你10次不同区间的金额你每次都要从头加一遍不累才怪。更聪明的做法是每天记一笔“从1号到今天的累计开销”这样问“5号到10号”直接用“1到10的累计”减去“1到4的累计”一秒钟心算完成。前缀和的核心直觉就是这个“累计账本”的思维模式。2. 前缀和数组的构建与数学原理2.1 定义什么是前缀和数组给定原数组 a[1..n]这里我故意采用 1-based 下标后面会说原因定义前缀和数组 pre[i] 表示原数组从第 1 个元素到第 i 个元素的累加和即pre[i] a[1] a[2] ... a[i]很容易得到一个递推关系pre[i] pre[i-1] a[i]前置边界条件是 pre[0] 0。这一步至关重要因为它是处理“从第一个元素开始”的查询时的防护栏我们待会会专门讲。有了 pre 数组之后任何区间 [L, R] 的和都可以用一次减法得到sum(L, R) pre[R] - pre[L-1]你可以亲手验一遍pre[R] 包含了 a[1] 到 a[R] 的和pre[L-1] 包含了 a[1] 到 a[L-1] 的和两者相减恰好留下 a[L] 到 a[R] 的部分。2.2 为什么 pre[0] 0 这么关键假设我们要查询区间 [1, R]也就是从第一个元素加到第 R 个元素。按公式 sum pre[R] - pre[L-1]这里 L 是 1所以需要 pre[0] 的值。如果 pre[0] 没有初始化为 0那么就会出现两种情况要么数组中不存在的 pre[0] 导致越界要么拿到一个未初始化的随机垃圾值导致结果完全错误。这就是为什么我强烈建议所有涉及前缀和的数组都采用 1-based 下标同时把 pre[0] 设为 0。省去一堆 if 边界判断代码更简洁也不容易错。2.3 复杂度对比与适用边界方法预处理耗时单次查询耗时总耗时q次查询额外空间暴力法0O(R-L1)O(nq)O(1)前缀和O(n)O(1)O(nq)O(n)从总耗时的量级来看前缀和几乎是无条件胜出的。它在竞赛中的适用边界很宽只要 n、q 在 10^5 到 10^6 量级前缀和就是稳定答案不过如果数组会频繁修改静态前缀和就会失效——某个元素变了后面所有 pre[i] 都得更新最坏可能 O(n)这时就应该考虑树状数组或线段树了。但今天的题目说的是“静态”所以前缀和就是标准答案。3. 完整代码实现与逐行解析3.1 一维前缀和的标准写法C先给出一份可以直接提交的代码#include bits/stdc.h using namespace std; const int N 100005; int a[N]; long long pre[N]; // 注意用 long long 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) { pre[i] pre[i - 1] a[i]; } while (q--) { int L, R; cin L R; cout pre[R] - pre[L - 1] \n; } return 0; }重点说几个细节。第一pre 数组为什么用 long long题目通常不会明说但输入数组元素范围可能是 int 级别的非负数n 可能上万甚至十万。如果 pre[i] 仍然用 int一旦累加结果超过约 21 亿就会溢出变成负值甚至乱值。秋招笔试题里经常有一批人挂在“int 溢出”上所以在累加类问题里前缀和数组无脑开 long long 是个好习惯。如果题目明确指出取模那就在累加的过程中同步取模注意减法后要加上 MOD 再取模一次避免出现负值。第二cin 的输入优化。如果 n、q、数组都是 10^5 量级其实普通 cin 也勉强能跑过但到了 10^6 量级关闭同步sync_with_stdio(false)就非常关键了它可以显著加快输入速度。也可以用 scanf / printf。在这道题里读入 q 组查询时用 cout 输出注意不能混用 printf 和 cout 且同时不关同步否则输出缓冲区可能混乱。3.2 一维前缀和的标准写法Python如果你用 Python 刷题同样很简单import sys input sys.stdin.readline n, q map(int, input().split()) a [0] list(map(int, input().split())) # 下标从1开始 pre [0] * (n 1) for i in range(1, n 1): pre[i] pre[i - 1] a[i] out_lines [] for _ in range(q): l, r map(int, input().split()) out_lines.append(str(pre[r] - pre[l - 1])) sys.stdout.write(\n.join(out_lines))注意 Python 版本里我用了一个常见小技巧a [0] list(...)直接把 dummy 元素放在最前面这样后面所有下标都天然从 1 开始不用手动改索引位置。输出也是统一收集到列表再用 sys.stdout.write 一次性写入避免循环里多次调用 print 造成的性能损耗。3.3 完整演示手算一遍流程假设输入数据如下5 3 1 3 7 2 6 1 5 2 4 3 3构建 pre 的过程pre[1] 0 1 1 pre[2] 1 3 4 pre[3] 4 7 11 pre[4] 11 2 13 pre[5] 13 6 19查询过程[1,5]: pre[5] - pre[0] 19 - 0 19 [2,4]: pre[4] - pre[1] 13 - 1 12 [3,3]: pre[3] - pre[2] 11 - 4 7和手工一个个加起来的结果完全一致。4. 踩坑经验数组越界、下标混乱与初始化陷阱4.1 0-based 下标最容易出的错网上许多代码和教材习惯用 0-based 下标即数组元素从 a[0] 到 a[n-1]前缀和定义为 pre[i] 表示“前 i 个元素之和”。这时查询区间 [l, r]同样 0-based的公式变成 sum pre[r1] - pre[l]。如果你没注意这个偏移很容易把代码写成 pre[r] - pre[l-1]在 l0 时 pre[-1] 直接越界。我见过很多同学在这上面来回调试最后把代码改成 1-based 之后突然就畅通无阻了。我个人强烈建议新手直接采用 1-based 下标这样可以完全屏蔽这些偏移错误把精力留在算法本身。4.2 输入格式的陷阱有时候下标是 0-based 的牛客的题目描述有时会说“下标从 0 开始”有时说“下标从 1 开始”这两种描述对应的输入范围不一样。如果你看到 L 和 R 的取值可能是 0那么请务必确认自己的 pre 数组是否有 pre[0] 的合理定义。在 1-based 版本中pre[0]0 天然覆盖了这种情况只是转换时要注意 L 是否该加 1。一个通用技巧写代码之前先在纸上写下“我的 pre 数组下标从几开始”然后带一组最小用例比如 n1 时查询 [1,1]手工走一遍确认边界没问题再提交。4.3 常见错误速查表错误类型典型表现解决方式pre 数组用 int 导致溢出结果莫名变成负数或巨大数字前缀和数组用 long long下标从0开始却用 pre[r] - pre[l-1]l0时越界或访问 pre[-1]统一1-based或改用 pre[r1]-pre[l]忘记 pre[0]0查询 [1,r] 时结果错误数组初始化为0多组数据未重置数组第二次运行结果累加上次残留while(T--)循环内重新初始化前缀和数组输入输出混用数据量大时TLE关闭同步或统一用 scanf/printfcout加上 \n 不要 endl第四个错误在比赛里很常见尤其是多组测试用例的题。如果你在一个大循环里重复使用全局数组下一次测试开始时 pre 数组里还残留着上一次的数据直接用就会出错。稳妥做法是每组数据都重新计算前缀和或者用 vector 在每次循环里重新长度清零。5. 从一维到二维矩形区间和的扩展5.1 二维前缀和的推导思路当题目升级到“给你一个二维矩阵多次查询某个子矩形的元素和”时一维版本的思路完全可以推广过来。定义二维前缀和矩阵 S[i][j] 表示从 (1,1) 到 (i,j) 这个矩形区域内所有元素的和。递推关系比一维稍复杂一点需要用到容斥原理S[i][j] S[i-1][j] S[i][j-1] - S[i-1][j-1] a[i][j]你可以这样理解S[i-1][j] 覆盖了上方所有行S[i][j-1] 覆盖了左边所有列两者相加把左上角 S[i-1][j-1] 这部分重复算了一次所以要减掉一次最后再把当前格子 a[i][j] 自己加上。查询子矩形x1,y1到x2,y2的和时同样用容斥sum S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] S[x1-1][y1-1]道理和构建时一模一样左上角被减了两次要再加回来一次。5.2 二维前缀和代码示例#include bits/stdc.h using namespace std; const int N 1005; int a[N][N]; long long S[N][N]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin n m q; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; } } for (int i 1; i n; i) { for (int j 1; j m; j) { S[i][j] S[i - 1][j] S[i][j - 1] - S[i - 1][j - 1] a[i][j]; } } while (q--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; long long ans S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] S[x1 - 1][y1 - 1]; cout ans \n; } return 0; }二维版本里的下标陷阱更隐蔽。构建 S 时如果省略了 S[i-1][j-1] 那一项会出现大面积重复计算结果会偏大查询时四个符号记错一个整个答案都会错。我的建议是把这个公式抄在代码注释上方每次写之前对照一遍。5.3 什么时候考虑二维前缀和二维前缀和适合矩阵规模在 10^3 量级、查询次数在 10^5 量级的题目。如果矩阵是 10^5×10^5 这种稀疏大矩阵显然无法开二维数组到时可能需要换用离散化或其他手段。总之看到“静态矩阵 矩形区域求和”这个组合第一时间就该想到二维前缀和。6. 变体题型前缀和绝不只能“求和”用6.1 前缀和与哈希表结合找特定区间前缀和并不只是“求某段和”这么死板。有一类高频面试题是给定数组问有多少个子数组的和等于 k。如果直接枚举区间是 O(n^2)但配合前缀和可以降到 O(n)。思路是任意区间和等于 pre[r] - pre[l-1]。如果要求和等于 k那就是 pre[r] - k pre[l-1]。在遍历的过程中用一个哈希表记录每个前缀和值出现的次数每到一个新位置 r就查一下 pre[r] - k 是否已经在哈希表里因为 pre[r]-k 就是之前某个 pre[l-1] 的值。这正好把“区间和等于 k”转化成了“两个前缀和之差等于 k”的计数问题。6.2 前缀和与差分互为逆运算如果你学过差分数组会发现差分和前缀和是一对互逆操作对原数组做差分得到 d对 d 做前缀和又能还原出原数组。差分常用于“多次区间统一加一个数最后再查询”的场景。很多复杂的题实际上就是先差分维护批量修改再做前缀和还原最终值。从刷题学习的角度看每学一个算法都试着去想一想它和已经学过的算法之间的关系。前缀和和差分、前缀和与滑动窗口、前缀和与哈希表这些组合会成倍扩展你的解题武器库。6.3 异或、乘积、布尔运算的前缀化前缀和的“和”其实不只是数值加法。你可以把“加”换成按位异或得到前缀异或数组用于快速求任意区间的异或和也可以换成乘法但要注意溢出和零元素问题甚至可以换成逻辑与或运算。只要运算满足区间可减性即能从整体结果中“扣除”某个前缀部分就能沿用前缀和思想。异或有个特别好的性质a ^ a 0所以区间异或和公式直接是 xor[r] ^ xor[l-1]连“减法”都省了非常清爽。遇到求区间异或和的题直接用前缀异或即可。7. 竞赛做题策略与总结心得7.1 拿到题目如何快速识别前缀和看到问题第一件事不要急着写代码先判断题型特征。适合前缀和的题通常有三个信号数组或矩阵是静态的没有修改操作有大量区间查询每次查的是和、异或或乘积等可累加可减的量题目时间复杂度卡得比较紧暴力解法明显会超时。如果数组中存在修改操作但修改次数很少比如小于 100你也可以折中处理每次修改后重新 O(n) 构建前缀和总复杂度依然可接受。这个思路在竞赛里很实用。7.2 实测过的一些稳定写法习惯代码规范化对竞赛做题有很大帮助。我个人的习惯是所有涉及下标的数组统一 1-based前缀和数组用 long long所有多组测试用例的循环里都重新初始化读入用关同步后的 cin 或直接用 scanf输出统一用 \n 而不是 endl避免不必要地刷新缓冲区。还有一个细节如果题目给的数据范围特别大比如 n 达到 10^6你预先开一个固定大小的全局数组会比动态 vector 更快因为 vector 会涉及内存申请不过固定数组大小要一次给足开 N 1000005 这类“范围上限 5”的值避免越界。7.3 这道每日一题还能怎么延伸从这道“静态区间和”继续挖下去你可以尝试这样进阶把数组改成“可修改”的版本用树状数组实现单点更新和区间查询把一维推到二维做矩形子矩阵和把查询改成“区间最大值/最小值”这时前缀和不够用得考虑线段树或稀疏表ST表把题目改成“有多少个区间和等于 k”练前缀和加哈希表的组合技。每一层延伸都会让你对前缀和思想的理解更深刻。这也是我推荐大家刷题不要只满足于 AC 的原因——把一道简单题吃透抵得上囫囵吞枣刷十道题。我个人在使用前缀和时最强烈的体会是很多看似繁琐的区间统计问题只要你愿意多花几分钟在“预处理”上往往就能换来后续查询的极大简化。这个思想不仅适用于竞赛处理日常数据统计、报表计算也同样高效——先把累计数据算好需要时做一次减法即可。别忘了下次看到“区间和”三个字先想想能不能用前缀和把复杂度从 O(nq) 降到 O(nq)这可能是你在这道题上最大的收获。