队员战斗力区间和计算的 C++ 实现

以下是使用 C++ 实现该功能的代码： ```cpp #include <iostream> using namespace std; const int MAXN = 100005; int a[MAXN], prefixSum[MAXN]; int main() { int n, m; // 读取队员数量 n 和考验次数 m cin >> n >> m; // 读取每个队员的战斗力，并计算前缀和 for (int i = 1; i <= n; i++) { cin >> a[i]; // 计算前缀和 prefixSum[i] = prefixSum[i - 1] + a[i]; } // 处理 m 次考验 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. **前缀和数组**：`prefixSum[i]` 表示从第 1 个队员到第 `i` 个队员的战斗力之和。通过遍历队员的战斗力数组 `a`，可以在 $O(n)$ 的时间内计算出前缀和数组。 2. **区间和计算**：对于每次考验的区间 `[L, R]`，可以通过 `prefixSum[R] - prefixSum[L - 1]` 快速计算出该区间内队员的战斗力之和。 3. **复杂度分析**：时间复杂度为 $O(n + m)$，其中 $n$ 是队员的数量，$m$ 是考验的次数。空间复杂度为 $O(n)$，主要用于存储前缀和数组。 ######[AI问答 | 449点数解答 | 2026-05-24 14:07:42]