C++ 利用前缀和解决队员战斗力区间求和问题

### 🍭思路分析 此问题同样适合使用前缀和的方法来高效解决。通过预先计算前缀和数组，能在 $O(1)$ 时间复杂度内计算出任意区间 `[L, R]` 的战斗力总和。 ### 🍬代码实现 ```cpp #include <iostream> #include <vector> int main() { int n, m; // 读取 n 和 m std::cin >> n >> m; // 存储每个队员的战斗力 std::vector<int> a(n + 1); // 存储前缀和 std::vector<int> prefixSum(n + 1, 0); // 读取每个队员的战斗力并计算前缀和 for (int i = 1; i <= n; ++i) { std::cin >> a[i]; // 计算前缀和 prefixSum[i] = prefixSum[i - 1] + a[i]; } // 处理 m 次查询 for (int i = 0; i < m; ++i) { int L, R; std::cin >> L >> R; // 计算区间 [L, R] 的战斗力总和 int result = prefixSum[R] - prefixSum[L - 1]; std::cout << result << std::endl; } return 0; } ``` ### 🍫代码解释 1. **输入处理**：首先读取队员数量 `n` 和查询次数 `m`，接着读取每个队员的战斗力存储在 `a` 数组中。 2. **前缀和计算**：创建 `prefixSum` 数组，`prefixSum[i]` 表示前 `i` 个队员的战斗力总和，通过 `prefixSum[i] = prefixSum[i - 1] + a[i]` 进行计算。 3. **查询处理**：对于每次查询，读取区间 `[L, R]`，利用 `prefixSum[R] - prefixSum[L - 1]` 计算该区间的战斗力总和并输出。 ### 🍮复杂度分析 - **时间复杂度**：计算前缀和数组的时间复杂度为 $O(n)$，每次查询的时间复杂度为 $O(1)$，所以总的时间复杂度为 $O(n + m)$。 - **空间复杂度**：需要额外的 $O(n)$ 空间来存储前缀和数组。 ### 🍰开发建议 - **输入验证**：在实际开发中，要对输入的 `n`、`m`、`L`、`R` 和 `a[i]` 进行合法性检查，避免出现越界等错误。 - **异常处理**：添加异常处理代码，例如输入格式错误等情况，增强程序的健壮性。 - **代码优化**：可以考虑对代码进行进一步优化，如减少不必要的变量使用，提高代码的执行效率。 ### 📘学习资源 - [C++ 官方文档](https://en.cppreference.com/w/)：提供了 C++ 语言的详细文档和教程。 - 《C++ Primer》：经典的 C++ 学习书籍，对 C++ 语言的各个方面有详细的介绍。 ######[AI写代码神器 | 737点数解答 | 2026-05-29 20:42:37]