C++前缀和实现区间和查询的高效算法

看到这个题目，你需要实现一个高效处理区间和查询的算法。由于 n 和 m 可能很大，直接遍历每个区间会超时。推荐使用**前缀和**预处理。 🧮 **前缀和思路** 前缀和数组 `pre[i]` 表示前 i 个数的和（`pre[0] = 0`）。那么区间 `[L, R]` 的和就等于 `pre[R] - pre[L - 1]`。预处理 O(n)，每次查询 O(1)，总复杂度 O(n + m)。 ✍️ **C++ 实现代码** ```cpp #include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<long long> a(n + 1, 0); vector<long long> pre(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } int m; cin >> m; while (m--) { int L, R; cin >> L >> R; cout << pre[R] - pre[L - 1] << '\n'; } return 0; } ``` 📝 **代码说明** - 用 `long long` 防止美丽值总和溢出（美丽值可能为负数或大整数）。 - `pre[i]` 直接从输入时构建，省去额外数组 `a` 也可以，但保留 `a` 更清晰。 - 使用 `ios::sync_with_stdio(false)` 和 `cin.tie(0)` 加速输入输出，应对大数据量。 ✅ **测试样例** 输入： ``` 5 1 2 3 4 5 3 1 3 2 4 1 5 ``` 输出： ``` 6 9 15 ``` ######[AI问答 | 446点数解答 | 2026-08-29 22:02:34]