区间浇水次数统计：差分数组与前缀和高效解法

这个问题是典型的**区间修改 + 区间查询**问题，可以使用**差分数组 + 前缀和**高效解决。 思路： - 对于每轮浇水，在差分数组 diff[L] += x，diff[R+1] -= x。 - 所有轮次结束后，对差分数组做前缀和，得到每朵花的实际浇水次数。 - 再对这个数组做前缀和，用于快速回答区间和查询。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; vector<long long> diff(n + 2, 0); // 区间修改：差分数组 for (int i = 0; i < q; i++) { int L, R; long long x; cin >> L >> R >> x; diff[L] += x; diff[R + 1] -= x; } // 前缀和得到每朵花的浇水次数 vector<long long> flower(n + 1, 0); for (int i = 1; i <= n; i++) { flower[i] = flower[i - 1] + diff[i]; } // 前缀和用于区间查询 vector<long long> prefix(n + 1, 0); for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + flower[i]; } int b, y; cin >> b >> y; cout << prefix[y] - prefix[b - 1] << endl; return 0; } ``` 时间复杂度 O(n + q)，空间复杂度 O(n)。 差分数组的引入避免了每次浇水都对区间内逐朵累加，能轻松应对 n 和 q 接近 100 甚至更大的数据。 ######[AI问答 | 416点数解答 | 2026-08-09 10:10:49]