C++实现花园花朵美丽值区间查询及优化方案

### 🌷思路分析 本题需要多次查询区间 `[L, R]` 内所有花的美丽值总和。可以先将每朵花的美丽值存储在数组中，然后对于每次查询，遍历该区间内的所有元素并求和。 ### 💻代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; // 输入花的数量 vector<int> a(n + 1); // 存储每朵花的美丽值，下标从 1 开始 for (int i = 1; i <= n; ++i) { cin >> a[i]; } int m; cin >> m; // 输入检测次数 for (int i = 0; i < m; ++i) { int L, R; cin >> L >> R; // 输入每次检测的区间 [L, R] int sum = 0; // 计算区间 [L, R] 内所有花的美丽值总和 for (int j = L; j <= R; ++j) { sum += a[j]; } cout << sum << endl; } return 0; } ``` ### 📝代码解释 1. **输入花的数量和美丽值**：首先读取花的数量 `n`，然后使用 `vector` 存储每朵花的美丽值，下标从 1 开始。 2. **输入检测次数**：读取检测次数 `m`。 3. **进行检测**：对于每次检测，读取区间 `[L, R]`，然后遍历该区间内的所有元素，将它们的美丽值相加，最后输出总和。 ### ⚙️复杂度分析 - **时间复杂度**：每次查询的时间复杂度为 $O(R - L + 1)$，对于 $m$ 次查询，总的时间复杂度为 $O(m * (R - L + 1))$。 - **空间复杂度**：主要用于存储每朵花的美丽值，空间复杂度为 $O(n)$。 ### 🚀进阶优化 如果查询次数较多，可以使用前缀和数组来优化查询时间。前缀和数组可以在 $O(1)$ 的时间内计算任意区间的和。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; // 输入花的数量 vector<int> a(n + 1); // 存储每朵花的美丽值，下标从 1 开始 vector<int> prefixSum(n + 1, 0); // 前缀和数组 for (int i = 1; i <= n; ++i) { cin >> a[i]; prefixSum[i] = prefixSum[i - 1] + a[i]; // 计算前缀和 } int m; cin >> m; // 输入检测次数 for (int i = 0; i < m; ++i) { int L, R; cin >> L >> R; // 输入每次检测的区间 [L, R] // 计算区间 [L, R] 内所有花的美丽值总和 int sum = prefixSum[R] - prefixSum[L - 1]; cout << sum << endl; } return 0; } ``` ### 🌟复杂度分析 - **时间复杂度**：预处理前缀和数组的时间复杂度为 $O(n)$，每次查询的时间复杂度为 $O(1)$，对于 $m$ 次查询，总的时间复杂度为 $O(n + m)$。 - **空间复杂度**：主要用于存储前缀和数组，空间复杂度为 $O(n)$。 ######[AI写代码神器 | 890点数解答 | 2026-05-29 20:07:25]