基于前缀和的高效区间求和算法C++实现

## 💡 解题思路 这是一个典型的**前缀和（Prefix Sum）**问题。直接对每个询问暴力求和，复杂度为 O(n*m)，在 n、m 均为 100000 时会超时。 用前缀和数组 pre[i] 表示前 i 个元素的战斗力之和，那么区间 [L, R] 的和等于 pre[R] - pre[L-1]。预处理 O(n)，每次查询 O(1)，总复杂度 O(n+m)，完全可行。 ## 🧠 算法步骤 1. 读入 n、m 和数组 a[1..n]。 2. 构建前缀和数组 pre[0]=0，pre[i]=pre[i-1]+a[i]。 3. 对每个询问 (L, R)，输出 pre[R] - pre[L-1]。 ## 💻 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n + 1); vector<long long> pre(n + 1, 0); // 前缀和可能会超过 int 范围（最大1000*100000=1e8，但在100000*1000=1e8内，int够用，但用long long更安全） for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; } while (m--) { int L, R; cin >> L >> R; cout << pre[R] - pre[L - 1] << '\n'; } return 0; } ``` ## ⚠️ 开发注意要点 - 使用 `ios::sync_with_stdio(false)` 和 `cin.tie(nullptr)` 加速输入输出，否则大数据量可能超时。 - 前缀和数组建议用 `long long`，虽然本题数据范围 int 足够，但这是通用安全写法。 - 数组下标从 1 开始，便于处理 pre[L-1]，避免边界判断。 - 输出用 `'\n'` 而不是 `endl`，减少刷新缓冲区的开销。 ######[AI问答 | 515点数解答 | 2026-08-29 21:20:00]