欢迎阅读 欢迎来到「前缀和区间求和」题解之旅本文将带你从快速回答数组任意区间的和这一直观场景出发深入理解前缀和的巧妙运用并掌握如何预处理前缀和数组来在 O(1) 时间内回答区间查询。在开始之前建议你先了解题目背景这是经典的一维前缀和模板题给定n个数和m次询问每次询问区间[l, r]的元素之和。本质上区间和 前缀和之差问题转化为预处理一次、查询直接相减。明确学习目标掌握前缀和数组的构建理解dp[r] - dp[l-1]的推导过程并熟练处理下标从 1 开始与long long 防溢出等边界情况。准备好环境建议在本地 IDE 中打开代码边看边运行亲手验证示例如n5数组1 3 5 7 9查询[2,4]输出15。本文将从问题转化、预处理、区间查询、边界防护到代码实现层层递进。即使你对前缀和还不熟悉我们也会从把每一段的路程先累计好问哪段减哪段这一直觉出发让你轻松抓住核心思想——前缀之差区间之和大减前。现在让我们一起预处理前缀和O(1) 回答每一次询问吧 ⚡个人主页愿旖旎专栏传送门算法专栏当前学习内容前缀和一.题目【模板】前缀和_牛客题霸_牛客网一、问题分析前置分析题目要求给定n个整数与m次询问每次输出区间 [l, r] 的和。关键约束n、m可能很大元素可能为大整数累加和可能超 int。核心思路暴力做法每次查询都要重新累加总代价 O(n·m) 无法接受前缀和一次性预处理前 i 项之和之后区间和 dp[r] - dp[l-1]一次减法 O(1) 得到答案总复杂度降为O(n m)。 例子暴力为什么不可行数组[1, 3, 5, 7, 9]一次查询[2, 4]需要重算3 5 7 15如果再来一次[1, 5]又要从 1 开始全部重加一遍。每次查询的累加都从头开始与之前算过的东西毫无复用——这就是暴力做法的根本浪费。二、算法策略前缀和预处理 差分查询核心步骤读入原数组v[1..n]存原始数据下标从 1 开始v[0]闲置。预处理前缀和dp[i] dp[i-1] v[i]含义为前 i 个元素之和。区间查询区间[l, r]的和 dp[r] - dp[l-1]。循环输出处理 m 次询问每次 O(1) 相减输出。 示例前缀和如何复用计算结果v [1, 3, 5, 7, 9]下标 i012345v[i]—13579dp[i]01491625构建时每个dp[i]都复用前一个dp[3] dp[2] 5查询时无论问哪个区间都只需一次相减[2,4]→16-115[1,5]→25-025[3,5]→25-421——算过一次的和永远不用重算这就是前缀和相对暴力的本质改进。三、正确性说明简单版本前缀和定义自洽dp[i] dp[i-1] v[i]递推保证dp[i]精确等于前 i 项之和递推无误差。区间差公式正确区间[l, r]的和 前 r 项之和 − 前 l-1 项之和公共部分完全抵消恰好剩下v[l] ... v[r]。下标从 1 起步安全dp[0] 0使l 1时公式退化为dp[r] - 0无需特判所有合法区间统一适用不漏不错。 例子公式为什么成立以单元素区间为例取[3, 3]dp[3] - dp[2] 9 - 4 5恰好等于v[3]。展开看(v1v2v3) - (v1v2) v3前两项完全抵消只剩区间内的元素——任意区间都等价于整体减前缀这正是公式的数学本质。四、实现细节边界防护初始化v、dp均开n1大小dp[0] 0默认。边界防护下标从 1 开始避免l-1越界dp[0] 0兜底查询[1, r]时公式仍统一累加和用long long4 个1e9相加达4e9已超 int 上限2.1e9大量查询时关闭流同步提升 IO 速度。复杂度时间 O(n m)预处理 O(n)每次查询 O(1)空间 O(n)两个数组。关键操作dp[i] dp[i-1] v[i]预处理、dp[r] - dp[l-1]区间查询公式。 例子long long 防溢出n4、元素全为1e9时dp[4] 4e9超出 int 上限2147483647int 会溢出为负数-294967296改用long long后正确得到4000000000——累加和类题目必须预估最大和超 int 就上 64 位。五、返回值目标映射每次查询输出dp[r] - dp[l-1]区间 [l, r] 的和对应题目输出每次询问的区间和。三.代码#include iostream #include vector using namespace std; int main() { ios::sync_with_stdio(false); // 关闭 C 与 C 流同步加速输入输出 cin.tie(0); // 解除 cin 与 cout 绑定避免频繁 flush long long n, m; // n 个元素m 次询问long long 防大数 cin n m; vectorlong long v(n 1); // 原数组下标从 1 开始v[0] 闲置 for (int i 1; i n; i) { cin v[i]; } // 1. 预处理前缀和dp[i] 前 i 个元素之和 vectorlong long dp(n 1); // dp[0] 0默认使 l1 时公式统一 for (int i 1; i n; i) { dp[i] dp[i - 1] v[i]; // 递推前 i 个 前 i-1 个 第 i 个 } // 2. 区间查询O(1) 回答每次询问 long long l, r; for (int i 0; i m; i) { cin l r; // 区间 [l, r] 的和 前 r 个的和 - 前 l-1 个的和 cout dp[r] - dp[l - 1] \n; // 用 \n 而非 endl避免逐行 flush } return 0; }四、易错点分析难点1下标必须从 1 开始且 dp[0] 要预留为 0vectorlong long v(n 1); // 开 n1 大小 vectorlong long dp(n 1); for (int i 1; i n; i) // 从 1 读到 n实例对比数组[1,3,5,7,9]查询[2,4]正确答案 15从 1 存v[1]1...v[5]9dp[4]-dp[1] 16-1 15✅ 。从 0 存v[0]1...v[4]9语义偏移一位容易把元素位置与下标搞混查错区间且l0时dp[-1]越界。结论多开一位、整体平移空间换边界安全。难点2区间和公式dp[r] - dp[l-1]的减数易写错cout dp[r] - dp[l - 1] \n;实例对比数组[1,3,5,7,9]查询[2,4]正确答案 15写法计算结果问题dp[r] - dp[l-1]16 - 115✅正确dp[r] - dp[l]16 - 412 ❌多减了 v[l]3dp[r-1] - dp[l-1]9 - 18 ❌漏掉了 v[r]7记忆口诀前 r 个减前 l-1 个——减数永远比左端点小 1。难点3累加和必须用 long longvectorlong long v(n 1); vectorlong long dp(n 1);实例n4元素全为1e9dp[4] 4e9 int 上限2,147,483,647用int溢出回绕为-294967296查询输出负数用long long正确得到4000000000。判断方法n × 元素最大值 2.1e9即需 64 位1e5 × 1e9 1e14竞赛题几乎必超直接上 long long 最稳。五、流程图 闭幕 恭喜你完成了「前缀和区间求和」问题的学习为了巩固知识并进一步拓展建议你动手实践在 牛客 上提交代码尝试不同的测试用例。深入思考本题通过预处理前缀和数组dp[i]将区间查询从 O(n) 降至O(1)。请问dp[i]的定义是什么为什么dp[0]必须为 0这对后续查询有什么便利区间[l, r]的和用dp[r] - dp[l-1]计算。如果区间是[1, n]或[1, 1]这个公式是否仍然成立请代入验证。预处理时间复杂度O(n)空间复杂度O(n)。如果m询问次数远小于n是否还有必要预计算前缀和能否改用其他策略如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案dp[i]表示原数组前 i 个元素之和即dp[i] v[1] v[2] ... v[i]。dp[0] 0是为了让l1时dp[l-1] dp[0] 0使公式dp[r] - dp[0]仍能正确返回[1, r]的和统一处理边界。公式完全成立[1, n]时dp[n] - dp[0] 总和[1, 1]时dp[1] - dp[0] v[1]正确。若m很小如 1 或 2预处理 O(n) 可能比每次直接累加 O(n) 还慢可直接每次循环累加或缓存答案但一般题目的m较大前缀和更优。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨