C++ 实现战斗力区间和查询问题

以下是解决该问题的 C++ 代码及详细 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; // 读取总人数 n 和考验次数 m cin >> n >> m; // 存储每个人的战斗力 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]; } for (int i = 0; i < m; ++i) { int L, R; // 读取每次考验的区间 [L, R] cin >> L >> R; // 计算区间 [L, R] 的战斗力之和 int sum = prefixSum[R] - prefixSum[L - 1]; // 输出结果 cout << sum << endl; } return 0; } ``` ### 代码解释： 1. **输入读取**：首先读取总人数 `n` 和考验次数 `m`，接着读取每个人的战斗力并存储在数组 `a` 中。 2. **前缀和数组计算**：创建前缀和数组 `prefixSum`，`prefixSum[i]` 表示前 `i` 个人的战斗力之和。通过遍历 `a` 数组，计算前缀和。 3. **区间和计算**：对于每次考验，读取区间 `[L, R]`，利用前缀和数组计算该区间的战斗力之和，即 `prefixSum[R] - prefixSum[L - 1]`。 4. **输出结果**：将每次考验的结果输出。 ### 复杂度分析： - **时间复杂度**：$O(n + m)$，其中 $n$ 是人数，$m$ 是考验次数。计算前缀和的时间复杂度为 $O(n)$，每次查询的时间复杂度为 $O(1)$，总共查询 $m$ 次。 - **空间复杂度**：$O(n)$，主要用于存储前缀和数组。 ######[AI问答 | 553点数解答 | 2026-05-30 19:34:46]