前缀和算法实现：C++高效区间求和解决方案

这是一个典型的**前缀和（Prefix Sum）**问题。对于单次查询（L, R）求区间和，如果每次直接遍历求和时间复杂度为 O(n)，m 次查询则达到 O(n*m)，在 n,m 最大为 100,000 时会超时。使用前缀和可以将每次查询优化到 O(1)，总时间复杂度降到 O(n + m)。 下面是完整的 C++ 解决方案： ## 🚀 前缀和算法实现 ```cpp #include <iostream> using namespace std; const int MAXN = 100005; long long prefixSum[MAXN]; // 前缀和数组，使用 long long 防止溢出 int main() { int n, m; cin >> n >> m; // 输入队员数和考验次数 // 构建前缀和数组 // prefixSum[i] 表示前 i 个人的战斗力总和（1-indexed） for (int i = 1; i <= n; i++) { int a; cin >> a; // 读入第 i 个人的战斗力 prefixSum[i] = prefixSum[i-1] + a; // 累加前 i 个的总和 } // 处理 m 次查询 while (m--) { int L, R; cin >> L >> R; // 区间 [L, R] 的和 = 前缀和[R] - 前缀和[L-1] long long sum = prefixSum[R] - prefixSum[L-1]; cout << sum << endl; } return 0; } ``` ## 📊 算法原理详解 | 部分 | 说明 | |------|------| | **前缀和定义** | `prefixSum[i]` 存储数组中第 1 个到第 i 个元素的总和 | | **核心公式** | 区间 `[L, R]` 的和 = `prefixSum[R] - prefixSum[L-1]` | | **数组下标** | 使用 1-indexed 方便理解，`prefixSum[0]` 初始化为 0 | | **数据类型** | 使用 `long long` 防止累加时数据溢出（n 最大 100,000，a[i] 最大 1000，总和最大 10^8，int 足够，但保险起见用 long long） | **时间复杂度分析：** - **构建前缀和**：O(n)，一次遍历即可 - **每次查询**：O(1)，只需两次数组访问和一次减法 - **总体复杂度**：O(n + m)，远优于暴力 O(n*m) ## 💡 代码优化与最佳实践 1. **输入输出优化**（当数据量较大时） ```cpp ios::sync_with_stdio(false); cin.tie(0); ``` 可以大幅提升 `cin/cout` 的速度，应对大数据量输入。 2. **完整优化版本**： ```cpp #include <iostream> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; long long prefix[100005] = {0}; for (int i = 1; i <= n; i++) { int val; cin >> val; prefix[i] = prefix[i-1] + val; } while (m--) { int L, R; cin >> L >> R; cout << prefix[R] - prefix[L-1] << '\n'; // 用 '\n' 代替 endl，减少刷新 } return 0; } ``` 3. **边界检查**：题目保证 `1 ≤ L ≤ R ≤ n`，无需额外检查，但生产中建议加上保护。 ## ⚠️ 常见陷阱 - **下标越界**：如果使用 0-indexed 但公式混淆，会导致错误，务必统一索引风格 - **溢出风险**：虽然这里 int 足够，但面对更大的数据时建议直接使用 `long long` - **换行符选择**：循环中输出大量数据时，用 `'\n'` 比 `endl` 快，因为 `endl` 会强制刷新缓冲区 ## 📚 进阶扩展 这道题是**前缀和思想的经典应用**，同类问题还包括： - **二维前缀和**：解决子矩阵求和问题 - **差分数组**：快速对区间进行增减操作 - **前缀异或**：解决区间异或问题 如果后续遇到需要**多次更新数组元素**的情况，前缀和就不适用了，需要改用**线段树（Segment Tree）**或**树状数组（Fenwick Tree）**。 ######[AI写代码神器 | 1048点数解答 | 2026-07-31 19:42:42]