差分数组实现区间多次累加（C++）

这道题本质是一个区间累加问题，暴力方法会对每轮区间内的花逐一增加，时间复杂度 O(n*q)，在大数据下性能差。 我们可以用 **差分数组** 来优化。差分数组 `diff[i]` 表示第 `i` 朵花与第 `i-1` 朵花浇水次数的差值。对区间 `[L, R]` 浇水一次，只需： ``` diff[L] += 1 diff[R+1] -= 1 ``` 最后通过前缀和还原每朵花的浇水次数。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; // 差分数组，下标从1开始，需要多开一位处理R+1 vector<int> diff(n + 2, 0); for (int i = 0; i < q; i++) { int L, R; cin >> L >> R; diff[L] += 1; diff[R + 1] -= 1; } // 前缀和还原原数组 vector<int> result(n + 1, 0); int current = 0; for (int i = 1; i <= n; i++) { current += diff[i]; result[i] = current; } // 输出 for (int i = 1; i <= n; i++) { if (i > 1) cout << " "; cout << result[i]; } cout << endl; return 0; } ``` ######[AI问答 | 368点数解答 | 2026-06-06 14:29:57]