高效求解后缀和：C++实现与算法解析

## 🔍 问题解析 这是一个典型的后缀和（suffix sum）查询问题。需要快速回答 m 次询问，每次询问从位置 k 到 n 的区间和。若直接暴力求和，单次询问最坏 O(n)，总复杂度 O(m*n) 会超时（n,m 最大 10^5）。 ## 💡 解题思路 预计算后缀和数组 `suf[i]`，表示从 i 到 n 的和。 `Suf[n+1] = 0`（方便边界） `Suf[i] = a[i] + suf[i+1]` 查询 k 时，直接输出 `suf[k]`，单次 O(1)。总复杂度 O(n+m)，符合要求。 ## 🧩 算法步骤 1. 读取 n, m 和数组 a。 2. 从 n 到 1 倒序遍历，计算 `suf[i]`。 3. 对每个询问 k，输出 `suf[k]`。 ## 🛠️ C++ 代码实现 ```cpp #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } vector<long long> suf(n + 2, 0); // 后缀和，索引从1到n+1 for (int i = n; i >= 1; --i) { suf[i] = suf[i + 1] + a[i]; } while (m--) { int k; cin >> k; cout << suf[k] << '\n'; } return 0; } ``` ## ✅ 复杂度分析 - 时间：O(n + m) - 空间：O(n) ## 📌 注意事项 - 使用 `long long` 存储和，因为 n 最大 10^5，a[i] 最大 1000，总和最大 10^8，int 足够，但用 long long 更保险。 - 用 `ios::sync_with_stdio(false)` 加速输入输出，避免超时。 ######[AI问答 | 528点数解答 | 2026-08-29 21:51:19]