优化C++代码：利用前缀和计算数组区间和

你提供的代码功能是读取数组`a`和询问数组`k`，对每个询问的`k[i]`，计算数组`a`中从第`k[i]`个元素到最后一个元素的和并输出。这段代码的时间复杂度较高，为$O(m\times n)$，可以使用前缀和来优化，将时间复杂度降低到$O(m + n)$。 ### 优化后的代码 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; // 存储数组a vector<int> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } // 计算前缀和数组 vector<int> prefixSum(n + 1, 0); for (int i = 1; i <= n; i++) { prefixSum[i] = prefixSum[i - 1] + a[i]; } // 存储询问的k vector<int> k(m); for (int i = 0; i < m; i++) { cin >> k[i]; } // 处理每次询问 for (int i = 0; i < m; i++) { // 利用前缀和计算区间和 int sum = prefixSum[n] - prefixSum[k[i] - 1]; cout << sum << endl; } return 0; } ``` ### 代码解释 1. **前缀和数组**：`prefixSum[i]`表示数组`a`中前`i`个元素的和。 2. **计算区间和**：对于询问的`k[i]`，从第`k[i]`个元素到第`n`个元素的和可以通过`prefixSum[n] - prefixSum[k[i] - 1]`计算得到。 ######[AI问答 | 466点数解答 | 2026-04-08 21:23:04]