C++ 前缀和实现区间查询高效解法

好的，这是一个非常经典的**前缀和（Prefix Sum）**问题。在 C++ 中实现可以高效解决大量查询，时间复杂度为 **O(n + m)**，远优于每次询问都循环累加的 O(n*m)。 下面我会分步骤为你讲解并给出完整代码。 --- ## 🧩 问题分析 **题目要求**： 对于每次询问 k，计算 `a[1] + a[2] + ... + a[k-1]` 的和。注意这里**不包括** `a[k]` 本身。 **数据范围**： - n, m 最大可达 100,000 - a[i] 最大 1000 - k 范围：2 ≤ k ≤ n+1 **核心思路**： 如果每次都重新求和，最坏情况复杂度为 O(n*m) = 10^10，完全不可行。 因此我们预处理一个**前缀和数组** `prefix`，其中 `prefix[i]` 表示前 i 个元素的和（即 `a[1]+...+a[i]`）。 那么对于询问 `k`，答案就是 `prefix[k-1]`。 --- ## 💻 C++ 实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<int> a(n + 1); // 下标从1开始，方便计算 vector<long long> prefix(n + 1, 0); // 前缀和，可能较大用 long long for (int i = 1; i <= n; i++) { cin >> a[i]; prefix[i] = prefix[i - 1] + a[i]; } while (m--) { int k; cin >> k; // 根据题意，k 在 [2, n+1] 之间，所以 k-1 在 [1, n] 范围内 cout << prefix[k - 1] << '\n'; } return 0; } ``` **代码解释**： - `ios::sync_with_stdio(false);` 和 `cin.tie(0);` 是加速输入输出，防止大数据时超时。 - `prefix[i]` 表示 `a[1] + a[2] + ... + a[i]`，所以 `prefix[0] = 0`。 - 每次查询 `k`，直接输出 `prefix[k-1]`。 --- ## 🔍 复杂度分析 | 操作 | 时间复杂度 | 说明 | |------|------------|------| | 前缀和预处理 | O(n) | 一次遍历构建 prefix 数组 | | 每次查询 | O(1) | 直接索引返回 | | 总复杂度 | O(n + m) | 满足 10^5 规模，非常快 | | 空间复杂度 | O(n) | 存储 a 和 prefix 数组 | --- ## 🚀 开发建议与最佳实践 - **使用 `long long`**：虽然 a[i] 最大 1000，但 n 最大 100000，总和最大可达 10^8（1e8），在 int 范围内，但为了安全扩展（比如以后修改范围），建议用 `long long`，避免溢出。 - **输入输出优化**：在算法竞赛或大数据场景下，务必加上 `ios::sync_with_stdio(false)`，否则 cin/cout 可能超时。 - **数组从 1 开始**：这样 `prefix[k-1]` 和题目描述完全吻合，减少边界错误。 - **边界检查**：题目保证 k 在有效范围，但实际开发中建议加一个 `if (k <= 0 || k > n+1)` 的保护性判断，提高健壮性。 - **扩展思考**：如果题目变成求 `a[l] + ... + a[r]` 的和，那么可以用 `prefix[r] - prefix[l-1]`。前缀和是很多区间查询问题的基石。 --- ## 📚 相关知识点 - **前缀和 (Prefix Sum)**：常用于静态数组的区间和查询，预处理 O(n)，查询 O(1)。 - **差分数组 (Difference Array)**：如果经常进行区间增减操作，差分数组是很好的选择。 - **树状数组 / 线段树**：如果数组会动态更新，则需要这些数据结构来维持高效查询。 --- ## ⚠️ 常见坑点 - **忘记处理 `a[0]`**：如果数组从 0 开始，务必要定义 `prefix[0] = 0`，否则越界。 - **大量使用 `endl`**：`endl` 会强制刷新缓冲区，非常慢。用 `'\n'` 替代。 - **不使用 `long long`**：在某些极端情况下（虽然本题不会）可能会溢出，养成好习惯。 --- ## 📖 推荐学习资源 - [C++ 官方文档 - 输入输出](https://en.cppreference.com/w/cpp/io) - [算法竞赛入门经典（刘汝佳）](https://book.douban.com/subject/25906920/) - [OI Wiki - 前缀和](https://oi-wiki.org/basic/prefix-sum/) --- ## 💡 开发建议 > 在实际编写这类算法题时，建议**先思考最优解法**，不要急着写代码。前缀和、差分、双指针等基础技巧需要熟练掌握，它们是很多复杂问题的基石。注意代码的**健壮性**和**可读性**，即使比赛代码，也尽量保持清晰的结构。 --- ######[AI写代码神器 | 1237点数解答 | 2026-07-31 19:36:57]