C++实现数组前缀和查询计算

### 🔍 思路分析 本题需要根据给定的整数数组 `a`，处理多次询问。每次询问会给出一个整数 `k`，要求计算 `a[1] - a[2] + a[3] - a[4] ... a[k]` 的结果。为了避免每次询问都重新计算，我们可以使用前缀和的思想，先计算出所有可能的前缀和，然后在每次询问时直接使用计算好的结果。 ### 💻 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; // 读取 n 和 m cin >> n >> m; vector<int> a(n + 1); // 读取数组 a for (int i = 1; i <= n; ++i) { cin >> a[i]; } vector<int> prefix_sum(n + 1, 0); // 计算前缀和 for (int i = 1; i <= n; ++i) { if (i % 2 == 1) { prefix_sum[i] = prefix_sum[i - 1] + a[i]; } else { prefix_sum[i] = prefix_sum[i - 1] - a[i]; } } // 处理 m 次询问 for (int i = 0; i < m; ++i) { int k; cin >> k; // 输出结果 cout << prefix_sum[k] << endl; } return 0; } ``` ### 📝 代码解释 1. **输入处理**：首先读取 `n` 和 `m`，分别表示数组的长度和询问的次数。然后读取数组 `a`。 2. **前缀和计算**：使用 `prefix_sum` 数组来存储前缀和。对于奇数位置的元素，将其加到前缀和中；对于偶数位置的元素，将其从前缀和中减去。 3. **询问处理**：对于每次询问，读取 `k`，并直接输出 `prefix_sum[k]` 的值。 ### ⚙️ 复杂度分析 - **时间复杂度**：计算前缀和的时间复杂度为 $O(n)$，处理每次询问的时间复杂度为 $O(1)$，因此总的时间复杂度为 $O(n + m)$。 - **空间复杂度**：使用了一个长度为 `n + 1` 的 `prefix_sum` 数组，因此空间复杂度为 $O(n)$。 ### 💡 开发建议 - **边界检查**：在实际应用中，需要检查输入的 `k` 是否在有效范围内，避免数组越界。 - **代码复用**：可以将前缀和的计算封装成一个函数，提高代码的复用性。 - **错误处理**：可以添加输入验证，确保输入的 `n`、`m` 和 `k` 都是合法的正整数。 ### 📚 学习资源 - [C++ 官方文档](https://en.cppreference.com/w/)：提供了 C++ 语言的详细文档和参考资料。 - [《C++ Primer》](https://book.douban.com/subject/5387457/)：一本经典的 C++ 入门书籍，适合初学者。 ######[AI写代码神器 | 762点数解答 | 2026-05-29 20:10:03]