C++交替加减前缀和查询高效实现

好的，这是一个非常经典的**前缀和（Prefix Sum）**变种问题，不过这里的操作是交替加减。下面我会用 C++ 给出一个简单高效的解法。 --- ## 🧠 问题分析与思路 题目要求对于每个询问 `k`，计算： ``` a[1] - a[2] + a[3] - a[4] + ... ± a[k] ``` 其中，奇数下标（1-based）为正，偶数下标为负。 为了避免每次询问都重新循环计算（那样会超时），我们需要**预处理**一个前缀数组 `prefix[i]` 表示前 `i` 个元素的交替和。 --- ## 📐 前缀和数组构建 我们定义： - `prefix[0] = 0` - 对于 `i` 从 1 到 `n`： - 如果 `i` 是奇数：`prefix[i] = prefix[i-1] + a[i]` - 如果 `i` 是偶数：`prefix[i] = prefix[i-1] - a[i]` 这样，对于每个询问 `k`，直接输出 `prefix[k]` 即可，**时间复杂度 O(1)**。 --- ## 💻 C++ 代码实现 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, m; cin >> n >> m; vector<long long> a(n + 1); // 1-based 存储 vector<long long> prefix(n + 1, 0); for (int i = 1; i <= n; i++) { cin >> a[i]; if (i % 2 == 1) { prefix[i] = prefix[i-1] + a[i]; // 奇数加 } else { prefix[i] = prefix[i-1] - a[i]; // 偶数减 } } while (m--) { int k; cin >> k; cout << prefix[k] << endl; } return 0; } ``` --- ## 📌 代码说明 - **`vector<long long>`** 用于存储数组和前缀和，因为结果可能超出 `int` 范围，使用 `long long` 更安全。 - **输入输出**：使用 `cin` / `cout`，如果数据量很大，可以考虑 `ios::sync_with_stdio(false)` 加速。 - **边界处理**：`prefix[0] = 0` 是基础情形，循环从 1 开始。 --- ## ⚙️ 时间复杂度与空间复杂度 - **预处理**：O(n) - **每次询问**：O(1) - **总复杂度**：O(n + m) - **空间复杂度**：O(n) --- ## 🔍 示例验证 输入： ``` 5 3 1 2 3 4 5 1 2 3 ``` 输出： ``` 1 -1 2 ``` 解释： - `k=1`: `1` - `k=2`: `1 - 2 = -1` - `k=3`: `1 - 2 + 3 = 2` --- ## 💡 开发建议 1. **使用 `long long` 而非 `int`**：交替累加可能导致数值过大，甚至负数下界，`long long` 更保险。 2. **考虑输入输出优化**：如果 n,m 很大（比如 10^5 以上），建议在 `main` 开头加入： ```cpp ios::sync_with_stdio(false); cin.tie(0); ``` 以加快读取速度。 3. **可以下推到 `prefix` 数组**：如果不希望额外开数组，可以一边读入一边构建，减少内存占用。 4. **注意数组下标**：题目中 `a[1]...a[n]` 是 1-based，所以 `vector` 要开 `n+1` 的空间，避免索引越界。 --- ######[AI写代码神器 | 881点数解答 | 2026-07-31 20:24:45]