桃子花园花美丽值区间求和问题的C++代码实现

以下是解决该问题的 C++ 代码： ```cpp #include <iostream> #include <vector> int main() { int n; std::cin >> n; // 存储每朵花的美丽值 std::vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { std::cin >> a[i]; } // 计算前缀和，prefix_sum[i] 表示前 i 朵花的美丽值总和 std::vector<int> prefix_sum(n + 1, 0); for (int i = 1; i <= n; ++i) { prefix_sum[i] = prefix_sum[i - 1] + a[i]; } int m; std::cin >> m; // 处理每次检测 for (int i = 0; i < m; ++i) { int L, R; std::cin >> L >> R; // 区间 [L, R] 的美丽值总和等于前 R 朵花的美丽值总和减去前 L - 1 朵花的美丽值总和 int sum = prefix_sum[R] - prefix_sum[L - 1]; std::cout << sum << std::endl; } return 0; } ``` ### 代码解释 1. **输入花的数量和美丽值**：先读入花的数量 `n`，然后读入每朵花的美丽值并存入数组 `a`。 2. **计算前缀和**：创建一个前缀和数组 `prefix_sum`，`prefix_sum[i]` 表示前 `i` 朵花的美丽值总和。通过遍历数组 `a`，计算出前缀和数组的值。 3. **输入检测次数和区间**：接着读入检测次数 `m`，对于每次检测，读入区间 `[L, R]`。 4. **计算区间和并输出**：利用前缀和数组计算出区间 `[L, R]` 内所有花的美丽值总和，即 `prefix_sum[R] - prefix_sum[L - 1]`，并输出结果。 ### 复杂度分析 - **时间复杂度**：计算前缀和的时间复杂度为 $O(n)$，每次查询的时间复杂度为 $O(1)$，总共进行 $m$ 次查询，因此总的时间复杂度为 $O(n + m)$。 - **空间复杂度**：使用了前缀和数组，空间复杂度为 $O(n)$。 ######[AI问答 | 597点数解答 | 2026-08-29 20:22:52]