C++实现区间求和：前缀和算法高效解答

这个问题是经典的区间求和问题，可以用前缀和（Prefix Sum）来高效解决。每次询问直接通过前缀和数组 O(1) 计算，总复杂度 O(n+q)。 📝 解题思路 先读入 n 和 q，然后读入 n 个鲜艳值，构建前缀和数组 prefix[i] 表示前 i 朵花的鲜艳值总和。 每次询问 L 和 R，答案就是 prefix[R] - prefix[L-1]。 💻 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> a(n + 1, 0); vector<int> prefix(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; prefix[i] = prefix[i - 1] + a[i]; } while (q--) { int L, R; cin >> L >> R; cout << prefix[R] - prefix[L - 1] << endl; } return 0; } ``` ✅ 代码说明 - `prefix[i]` 存储从第1朵到第i朵的鲜艳值总和。 - 每次询问输出 `prefix[R] - prefix[L-1]`，减去前 L-1 朵的和，即得到区间 [L, R] 的和。 - 使用 `vector` 动态分配，避免固定大小数组的越界风险。 ######[AI问答 | 354点数解答 | 2026-08-01 23:28:23]