前缀和算法高效解决花园花朵鲜艳值区间查询问题

```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; vector<long long> a(n + 1), prefix(n + 1, 0); // 读取花朵鲜艳值 for (int i = 1; i <= n; i++) { cin >> a[i]; } // 计算前缀和 for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + a[i]; } // 处理每次查询 while (q--) { int L, R; cin >> L >> R; // 计算区间和 long long sum = prefix[R] - prefix[L - 1]; cout << sum << endl; } return 0; } ``` 📝 **代码说明** - 使用 `vector<long long>` 存储鲜艳值和前缀和，避免整数溢出。 - 前缀和数组 `prefix[i]` 表示前 `i` 朵花的鲜艳值总和。 - 区间 `[L, R]` 的和通过 `prefix[R] - prefix[L - 1]` 计算，时间复杂度 O(1)。 - 输入格式：第一行输入 `n` 和 `q`，第二行输入 `n` 个鲜艳值，随后 `q` 行每行输入 `L` 和 `R`。 🎯 **示例运行** ``` 输入： 5 3 1 3 5 7 9 1 3 2 4 1 5 输出： 9 15 25 ``` ######[AI问答 | 387点数解答 | 2026-03-20 21:32:50]