C++前缀和优化数组区间求和问题详解

好的，我会用C++为您解决这个问题，并提供清晰的代码解释、性能分析以及开发建议。 ## 💡 问题分析 这是一个典型的**前缀和（Prefix Sum）**问题。 - 给定一个长度为 `n` 的数组和 `m` 次查询，每次查询需要输出从第1个元素到第 `k` 个元素的和。 - 直接每次查询都循环累加会导致 **O(m * n)** 的时间复杂度，在 n 和 m 都达到1000时（最坏100万次操作）虽然也能勉强通过，但**前缀和可以将每次查询优化到 O(1)**。 ## 💡 解法一：直接模拟（易懂但效率略低） 每次查询都重新累加前 k 个数。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<int> a(n + 1); // 使用1-based索引，方便理解 for (int i = 1; i <= n; ++i) { cin >> a[i]; } vector<int> queries(m); for (int i = 0; i < m; ++i) { cin >> queries[i]; } for (int k : queries) { int sum = 0; for (int i = 1; i <= k; ++i) { sum += a[i]; } cout << sum << endl; } return 0; } ``` **时间复杂度**：O(m * n) **空间复杂度**：O(n + m) --- ## 💡 解法二：前缀和优化（推荐，高效稳定） 预处理一个 `prefix` 数组，`prefix[i]` 表示 `a[1] + a[2] + ... + a[i]`。 这样每次查询只需直接输出 `prefix[k]`。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); // 加速输入输出 cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n + 1, 0); vector<int> prefix(n + 1, 0); // prefix[0] = 0 for (int i = 1; i <= n; ++i) { cin >> a[i]; prefix[i] = prefix[i - 1] + a[i]; // 累加前缀和 } for (int i = 0; i < m; ++i) { int k; cin >> k; cout << prefix[k] << '\n'; // 直接输出 } return 0; } ``` **时间复杂度**：O(n + m) **空间复杂度**：O(n) --- ## 💡 常用技巧与注意事项 1. **数组索引从1开始**： - 这样前缀和 `prefix[i]` 的含义更直观：前 i 个元素的和。 - 避免处理边界时写额外判断。 2. **使用 `ios::sync_with_stdio(false)` 和 `cin.tie(nullptr)`**： - 可以大幅提升 C++ 的 cin/cout 速度，避免因输入输出过大导致超时。 3. **使用 `'\n'` 代替 `endl`**： - `endl` 会强制刷新缓冲区，影响性能。在多次输出时建议用 `'\n'`。 4. **数据范围与溢出**： - 题目中 `n ≤ 1000`, `a[i] ≤ 1000`，最大和为 1000×1000=1,000,000，远小于 `int` 范围，所以直接用 `int` 即可。 --- ## 💡 开发建议 1. **养成用 `vector` 代替裸数组的习惯**，可以避免内存越界和动态分配问题。 2. **多思考“预处理”思想**：前缀和是很多区间查询问题的基石（如二维前缀和、差分数组等），掌握后可以解决更多复杂问题。 3. **测试时注意边界**： - 当 k = 1 时，输出第一个数。 - 当 k = n 时，输出所有数的和。 - 确认输入格式（第三行 m 个数可能在同一行，也可能跨行，上述代码都能正确处理）。 --- ######[AI写代码神器 | 975点数解答 | 2026-05-22 19:23:28]