C++ 实现对数组前缀和的多次询问计算

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; // 输入 n 和 m cin >> n >> m; // 存储数组 a vector<int> a(n + 1); // 存储前缀和 vector<int> prefixSum(n + 1, 0); // 输入数组 a 的元素 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; // 输出 a[1] 到 a[k - 1] 的和 cout << prefixSum[k - 1] << endl; } return 0; } ``` ### 代码解释 1. **输入处理**：首先读取 `n` 和 `m`，分别表示数组的长度和询问的次数。 2. **前缀和计算**：使用 `prefixSum` 数组来存储前缀和，`prefixSum[i]` 表示 `a[1]` 到 `a[i]` 的和。 3. **询问处理**：对于每次询问，读取 `k`，然后输出 `prefixSum[k - 1]`，即 `a[1]` 到 `a[k - 1]` 的和。 ### 复杂度分析 - **时间复杂度**：计算前缀和的时间复杂度为 $O(n)$，处理每次询问的时间复杂度为 $O(1)$，因此总的时间复杂度为 $O(n + m)$。 - **空间复杂度**：使用了 `prefixSum` 数组，空间复杂度为 $O(n)$。 ######[AI问答 | 461点数解答 | 2026-05-30 19:19:47]