C++ 前缀和实现区间查询问题

这个问题是一个典型的**区间求和**问题。因为数据范围较小（n, q < 100），我们可以直接用**前缀和**（Prefix Sum）算法来高效计算。 ### 🧠 解题思路 - 构建一个前缀和数组 `pre`，其中 `pre[i]` 表示从第1朵花到第i朵花的鲜艳值总和。 - 区间 `[L, R]` 的总和 = `pre[R] - pre[L-1]`。 - 每次查询的复杂度为 `O(1)`，整体复杂度 `O(n + q)`。 ### 💻 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> a(n + 1); // 下标从1开始 vector<int> pre(n + 1, 0); // 前缀和数组 // 读入花的鲜艳值 for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; // 构造前缀和 } // 处理每次查询 for (int i = 0; i < q; i++) { int L, R; cin >> L >> R; cout << pre[R] - pre[L - 1] << endl; } return 0; } ``` ### 🔍 代码说明 - 我们使用了一个**从1开始**的数组，避免处理边界问题时出错。 - `pre[i]` 存储了从下标1到下标i的所有鲜艳值之和。 - 对于每次询问 `[L, R]`，直接通过 `pre[R] - pre[L-1]` 得到结果，非常快。 ######[AI问答 | 415点数解答 | 2026-06-21 19:20:20]