C++前缀和高效解决区间求和查询

## 📝 问题解析 这道题要求快速回答前缀和查询。n 和 m 最大可达 100,000，若对每个询问都累加前 k-1 项，复杂度为 O(n*m)，会超时。利用前缀和数组，一次预处理 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(nullptr); int n, m; cin >> n >> m; vector<long long> prefix(n + 1, 0); // prefix[i] 表示前 i 个数的和 for (int i = 1; i <= n; ++i) { long long x; cin >> x; prefix[i] = prefix[i - 1] + x; } for (int i = 0; i < m; ++i) { int k; cin >> k; // 题目要求 a[1]+...+a[k-1] 的和，即 prefix[k-1] cout << prefix[k - 1] << '\n'; } return 0; } ``` ## 🔍 代码说明 - 使用 `vector<long long>` 存储前缀和，因为 a[i] 最大 1000，n 最大 100000，总和最大 1e8，int 足够，但用 long long 更安全。 - 输入输出使用 `ios::sync_with_stdio(false)` 和 `cin.tie(nullptr)` 加速，避免大数据量下超时。 - 每次询问的 k 范围是 2 到 n+1，因此 `k-1` 的范围是 1 到 n，不会越界。 ## 📊 复杂度分析 - 预处理前缀和：O(n) - 每次查询：O(1) - 总时间复杂度：O(n + m) - 空间复杂度：O(n) ######[AI问答 | 461点数解答 | 2026-08-29 20:52:39]