战斗力区间求和问题的C++代码实现

以下是实现该功能的C++代码： ```cpp #include <iostream> using namespace std; const int MAXN = 100005; int a[MAXN]; int prefixSum[MAXN]; // 前缀和数组 int main() { int 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; cin >> L >> R; // 计算区间[L, R]的战斗力之和 int sum = prefixSum[R] - prefixSum[L - 1]; cout << sum << endl; } return 0; } ``` ### 代码解释： - **前缀和数组**：为了快速计算区间 `[L, R]` 的和，我们使用前缀和数组 `prefixSum`。`prefixSum[i]` 表示前 `i` 个人的战斗力之和，即 `prefixSum[i] = a[1] + a[2] + ... + a[i]`。 - **计算前缀和**：在读取每个人的战斗力时，我们同时更新前缀和数组。对于第 `i` 个人，其前缀和为 `prefixSum[i] = prefixSum[i - 1] + a[i]`。 - **处理询问**：对于每次询问 `[L, R]`，区间 `[L, R]` 的和可以通过 `prefixSum[R] - prefixSum[L - 1]` 计算得到。 ### 复杂度分析： - **时间复杂度**：预处理前缀和的时间复杂度为 $O(n)$，每次询问的时间复杂度为 $O(1)$，因此总的时间复杂度为 $O(n + m)$。 - **空间复杂度**：需要额外的 $O(n)$ 空间来存储前缀和数组。 ######[AI问答 | 503点数解答 | 2026-08-01 19:34:31]