🚀 前缀和优化：高效处理大规模前缀和查询

📊 **问题分析** 题目要求高效处理多次前缀和查询，直接每次遍历计算会导致时间复杂度为 O(m*n)，在 n 和 m 均为 100,000 时会超时（10^10 次操作）。因此需使用**前缀和数组**预处理，将查询时间优化至 O(1)。 --- ### 🛠 **解决方案** 1. **预处理前缀和数组** - 定义 `prefix_sum[i]` 表示 `a[1] + a[2] + ... + a[i]`。 - 通过一次遍历计算 `prefix_sum`，时间复杂度 O(n)。 2. **处理查询** - 对于查询 `k`，答案为 `prefix_sum[k-1]`（注意数组索引从 0 开始）。 - 每次查询直接取数组值，时间复杂度 O(1)。 --- ### 💻 **代码实现** ```python n, m = map(int, input().split()) a = list(map(int, input().split())) queries = list(map(int, input().split())) # 计算前缀和数组 prefix_sum = [0] * (n + 1) # prefix_sum[0] = 0 方便处理 for i in range(1, n + 1): prefix_sum[i] = prefix_sum[i - 1] + a[i - 1] # 处理查询 for k in queries: print(prefix_sum[k - 1]) ``` --- ### 📌 **关键点解释** - **前缀和数组**：`prefix_sum[i]` 存储前 `i` 个元素的和，通过递推公式 `prefix_sum[i] = prefix_sum[i-1] + a[i-1]` 计算。 - **查询优化**：直接通过 `prefix_sum[k-1]` 获取结果，无需重复遍历。 - **边界处理**：`prefix_sum[0] = 0` 确保 `k=2` 时正确返回 `a[1]` 的和。 --- ### ⚡ **性能优化** - **时间复杂度**：预处理 O(n)，查询 O(m)，总复杂度 O(n + m)，满足 1000ms 限制。 - **空间复杂度**：O(n) 存储前缀和数组，100MB 内存足够。 --- ### 🚨 **常见陷阱** 1. **数组索引错误**： - Python 列表从 0 开始，而题目中 `a[1]` 对应 `a[0]`，需在计算时调整索引（如 `a[i-1]`）。 2. **前缀和初始值**： - `prefix_sum[0]` 必须初始化为 0，否则 `prefix_sum[1]` 会错误包含 `a[0]` 两次。 3. **查询范围**： - 题目保证 `2 ≤ k ≤ n+1`，因此 `k-1` 始终在 `[1, n]` 范围内，无需额外检查。 --- ### 📚 **学习资源** - [前缀和算法详解（LeetCode）](https://leetcode.com/explore/learn/card/array-and-string/203/introduction-to-array/1171/) - [Python 列表操作官方文档](https://docs.python.org/3/tutorial/datastructures.html) --- ######[AI写代码神器 | 830点数解答 | 2026-05-29 20:36:21]