C++ 前缀和 高频笔试考点 实用技巧 牛客 DP34 [模板] 前缀和 题解 每日一题

题目描述

题目链接：DP34 【模板】前缀和

示例 1：
输入：
5 3
1 2 3 4 5
1 2
2 4
3 5
输出：
3
9
12
解释：
第 1 次查询：第 1 到 2 个元素和为 1+2=3；
第 2 次查询：第 2 到 4 个元素和为 2+3+4=9；
第 3 次查询：第 3 到 5 个元素和为 3+4+5=12。

提示：
1 ≤ n, m ≤ 10^5
数组元素 num[i] 为整数（可能为正、负或零）
1 ≤ a ≤ b ≤ n

为什么这道题值得你花几分钟看懂？

无论你是算法初学者渴望夯实基础，还是求职者全力备战笔试，「前缀和」都是绝对绕不开的核心技巧——它从不是只存在于牛客DP模板题里的“理论知识点”，而是解决「区间求和」问题的“效率利器”，在80%的笔试场景中都能看到它的身影，实用性拉满。

从算法思维进阶的角度看，这道前缀和基础题，更是理解「预处理思想」的“最佳入门案例”：

1. 效率跃迁的关键：通过一次提前遍历计算（预处理），后续所有区间查询的时间复杂度将迎来质的改变——从“每次查询都依赖区间长度的 O(n)”，直接优化到“每次查询仅需固定操作的 O(1)”。
2. 核心思路的体现：这种“用提前存储的少量空间，换取高频操作效率飞跃”的「以空间换时间」逻辑，正是应对海量查询、高频计算类问题的核心。
3. 进阶学习的铺垫：掌握前缀和，更相当于为后续二维前缀和、差分等进阶技巧打下坚实基础，直接打通了高效处理区间问题的“第一关”。

前缀和

“前缀和”听起来有点抽象——但其实它特别好懂，就像咱们生活里“记账”“算总数”的逻辑，打个比方就能快速理解👇

1. 什么是前缀和？
假设你每天都花一点零花钱，然后记在本子上：

周一花了2块，周二花了3块，周三花了5块，周四花了4块。

现在想算“从周一到某天一共花了多少”，比如：

周一到周一：2块（仅当天花费）
周一到周二：2+3=5块（两天累计）
周一到周三：2+3+5=10块（三天累计）
周一到周四：2+3+5+4=14块（四天累计）

这些“从第一个时间点开始，累加到当前时间点的总和”，就是咱们说的“前缀和”——“前缀”指“前面的连续部分”，“和”指“累加的结果”。

特别说明：严格来讲，前缀和并非一个“完整算法”，而是一种“提升计算效率的技巧”，核心是通过提前存储中间结果，避免重复计算。

2. 前缀和的算法应用
这种生活逻辑如何迁移到算法中？以数组 nums = [2, 3, 5, 4]（对应上述每天零花钱）为例，我们可以构建一个“前缀和数组” dp，专门存储“从数组第一个元素开始，累加到当前位置的总和”。

（1）前缀和数组的定义与构建
为了简化计算（尤其是处理“从第一个元素开始的区间”），我们约定：

• dp[0] = 0（作为初始基准，后续会解释其作用）
• dp[1]：累加前1个元素（即 nums[1]）→ 2
• dp[2]：累加前2个元素（nums[1] + nums[2]）→ 5
• dp[3]：累加前3个元素（nums[1] + nums[2] + nums[3]）→ 10
• dp[4]：累加前4个元素（nums[1] + nums[2] + nums[3] + nums[4]）→ 14

此时，前缀和数组 dp = [0, 2, 5, 10, 14]，其核心递推公式为：
dp[i] = dp[i-1] + nums[i] （当前前缀和 = 前一个前缀和 + 原数组当前位置元素）

（2）区间和的计算逻辑
前缀和的核心价值，在于快速计算“原数组中任意区间 [a, b] 的和”。以上述数组为例：

• 若要计算 [2, 3]（第2到第3个元素）的和：nums[2] + nums[3] = 3 + 5 = 8
• 用前缀和计算：dp[3] - dp[1] = 10 - 2 = 8，结果完全一致。

其原理可理解为：
dp[b] 是“从第1个元素到第b个元素的总和”，dp[a-1] 是“从第1个元素到第a-1个元素的总和”，两者相减，恰好得到“从第a个元素到第b个元素的总和”。

因此，区间 [a, b] 的和公式为：
sum(a, b) = dp[b] - dp[a-1]

而我们约定 dp[0] = 0，正是为了处理“a=1”的场景（如计算 [1, 4] 的和：dp[4] - dp[0] = 14 - 0 = 14），无需额外调整逻辑。

3. 什么时候用前缀和？
当题目满足以下两个条件时，优先考虑前缀和技巧：

1. 核心需求是“区间求和”：如计算数组某段元素的和、矩阵某子区域的和等。
2. 查询次数较多：若仅需1次查询，暴力遍历与前缀和效率差异不大；但查询次数达到1e5级时，前缀和的O(1)查询优势会被无限放大。

4. 前缀和能省多少时间？
不用纠结复杂的时间复杂度公式，用具体数字直观感受：
假设原数组长度 n=1e5，查询次数 m=1e5，且每次查询均为 [1, n]（最坏情况）：

• 暴力解法：每次查询需遍历 n 个元素，总操作次数 = m * n = 1e5 * 1e5 = 1e10（计算机每秒约处理1e8次操作，此方案必超时）。
• 前缀和解法：先花 n=1e5 次操作构建前缀和数组，后续每次查询仅需1次减法，总操作次数 = n + m = 1e5 + 1e5 = 2e5（效率提升50000倍）。

前缀和与动态规划的深层关联

很多人在做这道题的时候或许都会疑惑：“前缀和为什么会出现在动态规划模板题里？”
其实两者的关联核心在于 “状态转移思想”，具体可从以下三点拆解：

1. 核心思想的共性：利用已有结果推导新结果
动态规划的核心逻辑是“将大问题拆解为小问题，用小问题的解推导大问题的解”，即通过“状态转移方程”复用已有计算结果。
前缀和本质是动态规划思想的“简化版”：

• 动态规划中的“状态”：对应前缀和数组 dp[i]（表示“前i个元素的累加和”这一状态）。
• 动态规划中的“状态转移”：对应前缀和的递推公式 dp[i] = dp[i-1] + nums[i]（用前i-1个元素的状态，推导前i个元素的状态）。

2. 差异：无“决策”环节
动态规划的关键特征是“存在决策选择”（如背包问题中“选或不选当前物品”），需要通过比较不同决策的收益来确定最优解；而前缀和的递推过程是“确定的”——计算 dp[i] 时，只需固定加上 nums[i]，无需任何决策，因此它更偏向“技巧”而非“完整动态规划算法”。

3. 进阶联系：动态规划借前缀和优化
在复杂动态规划问题中，前缀和常作为“子问题优化工具”出现。例如：

• 最长递增子序列的和：若需计算“以第i个元素结尾的所有递增子序列的和”，可通过前缀和快速统计满足条件的前序元素和，避免嵌套遍历。
• 二维动态规划的区间和：在矩阵类动态规划问题中，二维前缀和可快速计算任意子矩阵的和，降低状态转移的时间复杂度。

暴力解法

在学习前缀和之前，先明确暴力解法的逻辑与局限，才能更深刻地体会前缀和的价值。

1. 暴力解法思路
就是每次查询区间 [a, b] 时，从第 a 个元素开始遍历到第 b 个元素，逐元素累加求和。

2. 暴力解法的代码实现（C++）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> num(n + 1, 0);  // 1-based存储
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
    }
    // 处理m次查询，❌ 此处为超时关键：每次查询遍历O(n)元素
    while (m--) {
        int a, b, sum = 0;
        cin >> a >> b;
        // 遍历区间[a, b]累加
        for (int i = a; i <= b; i++) {
            sum += num[i];
        }
        cout << sum << '\n';
    }
    return 0;
}

3. 暴力解法的致命问题：超时 ※
当 n=1e5 且 m=1e5，且每次查询均为 [1, n] 时，总操作次数为 1e5 * 1e5 = 1e10，远超计算机每秒约1e8次的处理能力，必然导致超时。因此，必须通过前缀和进行优化。

前缀和的完整实现

1. 代码整体逻辑
前缀和解法分为三个核心步骤：
（1）输入加速配置：应对1e5级数据的输入效率问题。
（2）构建前缀和数组：通过一次遍历计算前缀和，完成预处理。
（3）处理查询：每次查询直接套用 dp[b] - dp[a-1] 公式，O(1)输出结果。

2. 完整代码（含详细注释）

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // ------------ 输入加速配置 ------------
    // 关闭cin与stdio的同步（默认同步会降低cin速度）
    ios::sync_with_stdio(false);
    // 解除cin与cout的绑定（避免cin等待cout刷新缓冲区）
    cin.tie(nullptr);

    // ------------ 变量定义 ------------
    int n, m;  // n：数组长度，m：查询次数
    cin >> n >> m;

    // 为什么用vector而非普通数组？
    // 1. vector自动管理内存，避免数组越界风险；
    // 2. 支持动态大小（本题虽固定大小，但养成良好习惯）；
    // 3. 初始化更便捷（直接指定初始值为0）。
    vector<long long> num(n + 1, 0);  // 原始数组（1-based，num[0]闲置）
    vector<long long> dp(n + 1, 0);   // 前缀和数组（dp[0] = 0，作为基准）

    // ------------ 构建前缀和数组 ------------
    for (int i = 1; i <= n; i++) {
        cin >> num[i];  // 读取原始数组第i个元素
        // 状态转移：前i个元素的和 = 前i-1个元素的和 + 当前元素
        dp[i] = dp[i - 1] + num[i];
    }

    // ------------ 处理m次查询 ------------
    while (m--) {  // m次循环，每次循环后m减1（等价于for(int i=0; i<m; i++)）
        int a, b;
        cin >> a >> b;  // 读取查询的区间[a, b]
        // 区间和 = 前b个元素和 - 前a-1个元素和
        cout << dp[b] - dp[a - 1] << '\n';  // 用'\n'而非endl（避免刷新缓冲区，提升速度）
    }

    return 0;
}

细节总结

通过对前缀和从原理到实现的拆解，我们可以提炼出几个关键细节，这些细节既是避免错误的核心，也是理解“预处理思想”的关键：

⭐1. 为什么前缀和数组要从 dp[0] = 0 开始？
这是前缀和设计中“简化边界处理”的核心技巧。若不设置 dp[0] = 0，当计算“从第1个元素到第b个元素”的和时（即 a=1），需要单独判断：

• 无 dp[0] 时：需写 if (a == 1) sum = dp[b]; else sum = dp[b] - dp[a-1];，增加逻辑复杂度；
• 有 dp[0] 时：直接套用 dp[b] - dp[a-1]，a=1 时自然对应 dp[b] - dp[0] = dp[b]，无需额外判断。
  本质是用一个“虚拟的初始基准”，将所有区间求和场景统一成同一公式，降低代码冗余和出错概率。

⭐2. 为什么原始数组和前缀和数组都要用 long long？
很多初学者会忽略“整数溢出”问题，认为“数组元素是int，前缀和也用int就行”，但实际当数据量较大时（如 n=1e5，每个元素=1e5），前缀和最大值会达到 1e10，远超 int 类型的上限（约2e9），导致结果变成负数或乱码。
结论：只要涉及“累加求和”且数据量可能超过1e4，就优先用 long long 存储——不仅是前缀和数组 dp，原始数组 num 也建议用 long long（避免单个元素较大时，累加过程中临时值溢出）。

⭐3. 1-based 下标 vs 0-based 下标，该怎么选？
两种下标方式均可实现前缀和，但对初学者而言，1-based 下标更友好，核心原因是“与题目输入逻辑对齐”：

• 题目中查询的 a 和 b 是“第a个到第b个元素”（天然1-based），1-based 存储时，原始数组 num[a] 就是题目中的“第a个元素”，无需转换；
• 0-based 存储时，需将查询的 a 转成 a-1、b 转成 b-1，再计算 dp[b] - dp[a-1]，多一步转换就多一步出错风险（如忘记减1导致区间偏移）。
  除非题目明确要求0-based输入，否则优先用1-based存储，让代码逻辑与题目描述直接对应。

⭐4. 输入输出优化为什么是“必选项”而非“可选优化”？
当 n 和 m 达到 1e5 级时，默认的 cin 和 cout 速度会成为瓶颈：

• 默认情况下，cin 与 stdio 同步以保证兼容性，导致输入速度比 scanf 慢3~5倍，1e5个数据读取会耗时超1秒；
• endl 会强制刷新输出缓冲区，每次输出都要额外操作，1e5次输出累积耗时会远超题目时间限制（通常1~2秒）。
  优化方案是“必写代码”：

ios::sync_with_stdio(false);  // 关闭cin与stdio同步，提升输入速度
cin.tie(nullptr);             // 解除cin与cout绑定，避免cin等待cout刷新
cout << ... << '\n';          // 用'\n'代替endl，仅换行不刷新缓冲区

⭐5. 前缀和的“时间-空间”权衡：值得吗？
前缀和的本质是“以空间换时间”——用一个额外的数组（空间复杂度 O(n)），换取查询效率从 O(n) 到 O(1) 的飞跃。这种权衡在“查询次数多”的场景下性价比极高：

• 若查询次数 m=1：暴力解法（O(n)）和前缀和（O(n) 预处理 + O(1) 查询）效率差不多，甚至暴力更省空间；
• 若查询次数 m=1e5：暴力解法总时间 O(n*m)=1e10（必超时），前缀和总时间 O(n+m)=2e5（轻松通过）。
  这也印证了“预处理思想”的核心：当某类操作需要被高频重复执行时，提前花一次时间预处理，后续每次操作的成本会被无限摊薄。

下一篇博客，我们将从 “一维区间求和” 升级到 “二维区域求和”，重点讲解 DP35 【模板】二维前缀和—— 它是前缀和技巧的进阶应用，核心依然是 “预处理思想”，但需要解决 “如何用二维数组存储前缀和”“如何推导子矩阵和公式” 等新问题。

如果这篇前缀和的博客，帮你打通了“区间求和”的任督二脉，解决了之前“暴力超时”“边界难处理”的困惑，别忘了花1秒给个点赞+关注呀！

接下来这段时间，我会聚焦“二维前缀和”展开更新——从原理推导到代码实现，再到笔试高频坑点，每一步都会讲得明明白白。能看到这里的你，一定是对算法真心感兴趣、想扎扎实实学好的朋友～关注我，咱们一步一个脚印打基础、啃难题，下次笔试再遇到区间相关问题，你也能轻松秒杀！

对了，如果你是第一次看我的博客也可以点开我主页逛逛，里面还有不少算法入门干货，说不定会有你刚好需要的惊喜呢～