C++ 利用前缀和解决多次区间求和询问问题

### 🔍问题分析 本题的目标是进行多次询问，每次询问给出一个数 `k`，要求计算数组 `a` 中前 `k - 1` 个元素的和。为了避免每次询问都重新计算前 `k - 1` 个元素的和，我们可以使用前缀和的方法，先预处理出数组的前缀和，这样每次询问就可以在 $O(1)$ 的时间复杂度内得到结果。 ### 💻代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; // 输入数字的个数 n 和询问的次数 m cin >> n >> m; vector<int> a(n + 1); vector<int> prefixSum(n + 1, 0); // 输入 n 个数字 for (int i = 1; i <= n; ++i) { cin >> a[i]; // 计算前缀和 prefixSum[i] = prefixSum[i - 1] + a[i]; } // 进行 m 次询问 for (int i = 0; i < m; ++i) { int k; cin >> k; // 输出前 k - 1 个元素的和 cout << prefixSum[k - 1] << endl; } return 0; } ``` ### 📝代码解释 1. **输入处理**：首先读取数字的个数 `n` 和询问的次数 `m`，然后使用 `vector` 存储数组 `a` 和前缀和数组 `prefixSum`。 2. **前缀和计算**：通过循环遍历数组 `a`，计算前缀和数组 `prefixSum`。`prefixSum[i]` 表示数组 `a` 中前 `i` 个元素的和。 3. **询问处理**：对于每次询问，读取 `k`，并输出 `prefixSum[k - 1]`，即数组 `a` 中前 `k - 1` 个元素的和。 ### ⚙️复杂度分析 - **时间复杂度**：预处理前缀和的时间复杂度为 $O(n)$，每次询问的时间复杂度为 $O(1)$，因此总的时间复杂度为 $O(n + m)$。 - **空间复杂度**：需要额外的 $O(n)$ 空间来存储前缀和数组。 ### 🚀开发建议 - **边界检查**：在实际应用中，需要检查输入的 `k` 是否在合法范围内，避免数组越界。 - **数据类型**：如果数组元素和前缀和可能会超出 `int` 的范围，建议使用 `long long` 类型。 - **代码可读性**：可以将前缀和的计算和询问处理封装成函数，提高代码的可读性和可维护性。 ### 📚学习资源 - [C++ 官方文档](https://en.cppreference.com/w/)：提供了 C++ 语言的详细文档和参考资料。 - [《C++ Primer》](https://book.douban.com/subject/5387457/)：一本经典的 C++ 入门书籍，适合初学者学习。 ######[AI写代码神器 | 742点数解答 | 2026-08-01 20:31:51]