C++ 前缀交替和求解区间交替运算问题

## 🧮 问题理解 题目要求对数组前 k 项进行交替加减运算：`a[1] - a[2] + a[3] - a[4] + ...`。直接对每次询问从 1 到 k 遍历计算会超时（若 m 和 n 都很大）。最佳方案是预处理前缀交替和，将每次询问的复杂度降为 O(1)。 ## 💡 核心思路 定义前缀交替和数组 `pre[i]`，表示前 i 项的交替运算结果。 递推公式： - 当 i 为奇数时，`pre[i] = pre[i-1] + a[i]` - 当 i 为偶数时，`pre[i] = pre[i-1] - a[i]` 那么每次询问 k，直接输出 `pre[k]` 即可。 ## 🧪 输入输出示例 输入： ``` 5 3 1 2 3 4 5 1 3 5 ``` 计算过程： - pre[1] = 1 - pre[2] = 1 - 2 = -1 - pre[3] = -1 + 3 = 2 - pre[4] = 2 - 4 = -2 - pre[5] = -2 + 5 = 3 输出： ``` 1 2 3 ``` ## 📝 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> a(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; } vector<long long> pre(n + 1, 0); for (int i = 1; i <= n; i++) { if (i % 2 == 1) { pre[i] = pre[i - 1] + a[i]; } else { pre[i] = pre[i - 1] - a[i]; } } for (int q = 0; q < m; q++) { int k; cin >> k; cout << pre[k] << '\n'; } return 0; } ``` ## ⚙️ 复杂度分析 - 预处理：O(n) - 每次询问：O(1) - 总时间复杂度：O(n + m) - 空间复杂度：O(n) ######[AI问答 | 577点数解答 | 2026-08-29 22:07:28]