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

```cpp #include <iostream> using namespace std; int main() { int n, m; cin >> n >> m; int a[100001]; int prefixSum[100001] = {0}; for (int i = 1; i <= n; ++i) { cin >> a[i]; prefixSum[i] = prefixSum[i - 1] + a[i]; } for (int i = 0; i < m; ++i) { int L, R; cin >> L >> R; cout << prefixSum[R] - prefixSum[L - 1] << endl; } return 0; } ``` ### 代码解释 1. **输入部分**：先读取队员数量 `n` 和考验次数 `m`。接着读取每个队员的战斗力 `a[i]`，同时计算前缀和数组 `prefixSum`，`prefixSum[i]` 表示前 `i` 个队员的战斗力总和。 2. **询问处理**：对于每次考验，读取区间 `[L, R]`，通过 `prefixSum[R] - prefixSum[L - 1]` 计算出该区间内队员的战斗力之和并输出。 ### 复杂度分析 - **时间复杂度**：计算前缀和的时间复杂度是 $O(n)$，每次询问的时间复杂度是 $O(1)$，所以总的时间复杂度为 $O(n + m)$。 - **空间复杂度**：使用了前缀和数组，空间复杂度为 $O(n)$。 ######[AI问答 | 382点数解答 | 2026-05-30 19:24:50]