C++ 实现区间浇水次数累加及查询：差分与前缀和优化详解

这道题是一个典型的**区间累加 + 区间查询**问题。虽然数据规模较小（n<100，q可能也较小），但我们可以用一种高效的方法来做：**差分数组 + 前缀和**。 下面我会详细讲解两种解法： 1. **朴素模拟法**（适用于本题小规模数据） 2. **差分 + 前缀和优化法**（适用于大规模数据，推荐掌握） --- ## 🧩 解法一：朴素模拟法（直接暴力） ### ✅ 思路 - 开一个数组 `a[1..n]`，初始全为0。 - 对每一轮浇水 `(L, R, x)`，用循环将 `a[L]` 到 `a[R]` 每个加上 `x`。 - 最后对区间 `[b, y]` 求和并输出。 ### ✅ C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int n, q; cin >> n >> q; int a[105] = {0}; // 花浇水次数数组，下标从1开始 for (int i = 0; i < q; i++) { int L, R, x; cin >> L >> R >> x; for (int j = L; j <= R; j++) { a[j] += x; } } int b, y; cin >> b >> y; int sum = 0; for (int i = b; i <= y; i++) { sum += a[i]; } cout << sum << endl; return 0; } ``` ### ⏱ 复杂度分析 - 时间：O(q × 区间长度)，最坏 O(q × n) - 空间：O(n) **适用于本题**（n < 100，数据量小）。 --- ## 🧩 解法二：差分 + 前缀和（推荐） 这种方法即使数据规模变大（比如 n=10⁵, q=10⁵），也能高效运行。 ### ✅ 原理 - **差分数组** `diff[i]`：记录相邻两朵花浇水次数的差值。 - 对区间 `[L, R]` 增加 `x`： `diff[L] += x` `diff[R+1] -= x` - 然后通过**前缀和**还原出每朵花的实际浇水次数： ``` a[i] = a[i-1] + diff[i] ``` - 最后对区间 `[b, y]` 求前缀和。 ### ✅ 步骤 1. 初始化 `diff` 数组全为0。 2. 对每一轮 `(L, R, x)`： - `diff[L] += x` - `diff[R+1] -= x` 3. 计算 `a[1..n]`： - `a[i] = a[i-1] + diff[i]` 4. 计算 `prefix[0..n]`： - `prefix[i] = prefix[i-1] + a[i]` 5. 输出 `prefix[y] - prefix[b-1]` ### ✅ C++ 代码实现 ```cpp #include <iostream> using namespace std; int main() { int n, q; cin >> n >> q; int diff[105] = {0}; // 差分数组，大小比n大1 for (int i = 0; i < q; i++) { int L, R, x; cin >> L >> R >> x; diff[L] += x; diff[R + 1] -= x; } int a[105] = {0}; // 每朵花的实际浇水次数 int prefix[105] = {0}; // 前缀和数组 for (int i = 1; i <= n; i++) { a[i] = a[i-1] + diff[i]; prefix[i] = prefix[i-1] + a[i]; } int b, y; cin >> b >> y; cout << prefix[y] - prefix[b-1] << endl; return 0; } ``` ### ⏱ 复杂度分析 - 时间：O(n + q) - 空间：O(n) **即使 n=1000万，q=1000万，也能轻松运行。** --- ## ✅ 两种方法对比 | 方法 | 时间复杂度 | 空间复杂度 | 适用场景 | |------|------------|------------|----------| | 朴素模拟 | O(q × 区间长度) | O(n) | 小规模数据（n,q<1000） | | 差分+前缀和 | O(n + q) | O(n) | 大规模数据（n,q可达10⁵+） | --- ## ⚠️ 常见陷阱与注意事项 1. **数组下标从1开始**：题目中花编号从1到n，建议数组下标也从1开始，避免混淆。 2. **差分数组边界**：`diff[R+1]` 容易越界，记得数组大小设为 `n+2`。 3. **前缀和查询公式**：`[b, y]` 的和 = `prefix[y] - prefix[b-1]`，不要忘记 `b-1`。 4. **数据类型**：如果浇水次数 x 很大（比如 x ≤ 10⁹），建议使用 `long long` 类型。 --- ## 📘 开发建议 - **优先掌握差分+前缀和**：这是处理区间多次修改+单次/多次查询的经典技巧。 - **输入输出加速**：如果数据量大，可加上： ```cpp ios::sync_with_stdio(false); cin.tie(nullptr); ``` - **代码模块化**：可以将差分更新、前缀和生成、区间查询封装成函数，提高可读性。 - **测试用例**：除了题目样例，建议测试边界情况，如： - 浇水区间覆盖全部花。 - 查询区间只有一朵花。 - b == y。 --- 如果你需要我帮你用 Python、Java 或其他语言实现，或者想要我讲解差分/前缀和的底层原理，欢迎继续提问！ ######[AI写代码神器 | 1383点数解答 | 2026-06-06 21:28:22]