使用前缀和解决多次区间和查询问题

### 🍎思路分析 本题可以使用前缀和的方法来解决。前缀和是一种预处理数组的技巧，通过计算数组的前缀和，可以在 $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); // 读取数组元素并计算前缀和 for (int i = 1; i <= n; ++i) { cin >> a[i]; // 计算前缀和 prefixSum[i] = prefixSum[i - 1] + a[i]; } // 处理询问 for (int i = 0; i < m; ++i) { int k; cin >> k; // 输出前缀和 cout << prefixSum[k - 1] << endl; } return 0; } ``` ### 🍓代码解释 1. **输入处理**：首先读取 `n` 和 `m`，分别表示数组的长度和询问的次数。然后读取数组元素，并计算前缀和数组 `prefixSum`。 2. **前缀和计算**：`prefixSum[i]` 表示数组 `a` 中前 `i` 个元素的和。通过 `prefixSum[i] = prefixSum[i - 1] + a[i]` 计算前缀和。 3. **询问处理**：对于每次询问，读取 `k`，并输出 `prefixSum[k - 1]`，即 `a[1] + a[2] + ... + a[k - 1]` 的和。 ### 🍋复杂度分析 - **时间复杂度**：预处理前缀和数组的时间复杂度为 $O(n)$，每次询问的时间复杂度为 $O(1)$，因此总的时间复杂度为 $O(n + m)$。 - **空间复杂度**：需要额外的 $O(n)$ 空间来存储前缀和数组。 ### 🍉开发建议 - **边界检查**：在实际应用中，需要对输入的 `k` 进行边界检查，确保 `k` 在合法范围内。 - **错误处理**：可以添加错误处理代码，处理输入异常的情况，如输入的 `n`、`m` 或 `k` 不合法。 - **代码优化**：可以使用更高效的数据结构或算法来处理大规模数据。 ######[AI写代码神器 | 621点数解答 | 2026-05-29 20:37:17]