C++差分数组高效解决区间累加问题

这个问题是一个典型的差分数组（Difference Array）或前缀和（Prefix Sum）的应用场景。每轮浇水相当于对区间 `[L, R]` 内所有元素加 1，最后需要输出每个位置的累计值。 直接使用暴力累加（每轮遍历区间）在 q 和 n 较大时会超时，因此用差分数组优化到 O(n + q) 时间复杂度。 以下是 C++ 代码实现，包含详细 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; // 差分数组，大小 n+2，避免边界溢出 vector<int> diff(n + 2, 0); // 处理 q 轮浇水 for (int i = 0; i < q; i++) { int L, R; cin >> L >> R; // 差分操作：左端点加 1，右端点后一位减 1 diff[L] += 1; diff[R + 1] -= 1; } // 通过前缀和还原每一朵花的浇水次数 vector<int> result(n + 1, 0); for (int i = 1; i <= n; i++) { result[i] = result[i - 1] + diff[i]; } // 输出结果，用空格隔开 for (int i = 1; i <= n; i++) { if (i > 1) cout << " "; cout << result[i]; } cout << endl; return 0; } ``` ✅ **代码要点说明** - `diff` 数组长度设为 `n+2`，防止 `R+1` 越界。 - 差分操作：`diff[L]++` 表示从 L 开始累计增加，`diff[R+1]--` 表示到 R+1 处停止增加。 - 最终通过一次前缀和遍历，得到每个位置的实际浇水次数。 - 输入输出采用标准格式，支持多组测试（题目未明确，但代码可重复运行）。 **示例运行** 输入： ``` 5 3 1 3 2 4 3 5 ``` 输出： ``` 1 2 3 2 1 ``` （每朵花依次被浇 1, 2, 3, 2, 1 次） ######[AI问答 | 547点数解答 | 2026-08-02 15:11:50]