C++ 前缀和算法：高效解决区间和查询问题

好的，这个问题是一个典型的 **区间求和** 问题。如果每次询问都从L到R循环累加，当n和m都很大（比如10万）时，时间复杂度会达到O(n*m)，会超时。 **高效解法**：使用 **前缀和** (Prefix Sum) 技术。 ### 🎯 核心概念：前缀和 前缀和数组 `prefix[i]` 表示原数组 `a[1]` 到 `a[i]` 的元素之和。 - 定义：`prefix[0] = 0` - 递推：`prefix[i] = prefix[i-1] + a[i]` 这样，区间 `[L, R]` 的和就可以通过 **O(1)** 时间计算出来： `sum(L, R) = prefix[R] - prefix[L-1]` ### 📝 解题步骤 1. **读取输入**：读取n, m, 以及数组a。 2. **构建前缀和数组**： - 创建一个数组 `prefix`，长度为 `n+1`。 - `prefix[0] = 0`。 - 循环 `i` 从 1 到 n: `prefix[i] = prefix[i-1] + a[i]`。 3. **处理每次查询**：对于每个询问 `L, R`： - 直接计算并输出 `prefix[R] - prefix[L-1]`。 ### 💻 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; // 1. 读取原数组 (从下标1开始存储，方便与L,R对应) vector<int> a(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; } // 2. 构建前缀和数组 prefix // prefix[i] 表示 a[1] 到 a[i] 的和 vector<long long> prefix(n + 1, 0); // 使用 long long 防止和溢出 for (int i = 1; i <= n; ++i) { prefix[i] = prefix[i - 1] + a[i]; } // 3. 处理 m 次查询 for (int i = 0; i < m; ++i) { int L, R; cin >> L >> R; // 区间 [L, R] 的和 = prefix[R] - prefix[L-1] long long result = prefix[R] - prefix[L - 1]; cout << result << '\n'; // 使用 '\n' 比 endl 快 } return 0; } ``` ### ⚙️ 代码详解 - **`ios::sync_with_stdio(false); cin.tie(nullptr);`**： - 这两行代码用于 **解绑** C++ 标准输入输出流和 C 标准输入输出流，可以显著提升 `cin` 和 `cout` 的速度。在处理 10万级别数据时是必备优化。 - **`vector<long long> prefix(n + 1, 0);`**： - 使用 `long long` 类型，因为 `n` 最大为 10万，`a[i]` 最大为 1000，最大和可能达到 `100000 * 1000 = 1e8`，在 `int` 范围内，但为了安全（防止未来数据放大或过度累加），使用 `long long` 是最佳实践。 - **`prefix[i] = prefix[i-1] + a[i];`**： - 这是构建前缀和的核心递推公式。 - **`prefix[R] - prefix[L-1]`**： - 这是计算区间和的核心公式，时间复杂度为 O(1)。如果 `L=1`，那么结果就是 `prefix[R] - prefix[0] = prefix[R]`。 ### 🎯 复杂度分析 - **时间复杂度**：O(n + m) - 构建前缀和需要 O(n)。 - 每次查询是 O(1)，m 次查询是 O(m)。 - 远比每次查询都重新求和（O(n*m)）高效。 ### 💡 进阶使用与开发建议 1. **处理数据范围**： - 如果 `a[i]` 的范围更大（例如，10^9），或者 `n` 更大，那么前缀和数组一定要使用 `long long` (64-bit) 甚至 `unsigned long long`，以防止溢出。C++中 `int` 最大值约 21亿，很容易溢出。 2. **扩展应用：二维前缀和**： - 这个问题可以扩展到二维矩阵。如果有一个二维矩阵，需要频繁查询一个子矩阵的和，就可以使用 **二维前缀和**。 - 二维前缀和公式：`prefix[i][j] = a[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]` - 子矩阵 `(x1,y1)` 到 `(x2,y2)` 的和公式：`sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]` 3. **差分数组**（逆操作）： - 如果问题变成：对数组的某个区间 [L, R] 统一加上一个值 v，然后问最终数组。这种场景适合用 **差分数组**。差分数组是前缀和的逆运算。 4. **避免常见陷阱**： - **下标从1开始**：为了公式 `prefix[R] - prefix[L-1]` 的简便，建议数组和前缀和数组都从下标 **1** 开始，下标0填充0。这样可以免去对 L=1 的特殊判断。 - **输入输出效率**：在竞赛编程中，如果数据量大，`cin/cout` 不加优化会非常慢。务必加上 `ios::sync_with_stdio(false); cin.tie(nullptr);`，并在输出时使用 `'\n'` 而不是 `endl`（`endl` 会额外刷新缓冲区）。 5. **备选方案（适用于支持高并发的场景）**： - **线段树** 或 **树状数组 (Fenwick Tree)**：如果数据是**动态更新**的（即数组中的值会修改，同时查询区间和），那么前缀和就不适用了（因为每次修改都要 O(n) 重新构建前缀和）。此时应该使用线段树（O(log n) 修改和查询）或树状数组（适用于单点修改+区间查询）。 ### 📚 学习资源推荐 - **理论基础**：学习“前缀和与差分”是算法竞赛的基础，可以查阅 《算法竞赛入门经典》（刘汝佳） 或 《挑战程序设计竞赛》。 - **在线练习**：可以在 LeetCode 或 洛谷 上搜索 “前缀和”、“区间求和” 等标签进行练习。 ######[AI写代码神器 | 1608点数解答 | 2026-05-22 19:49:21]