花园浇水问题：差分数组与前缀和高效解法

```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> flowers(n + 1, 0); vector<long long> prefixSum(n + 1, 0); for (int i = 0; i < q; i++) { int L, R, x; cin >> L >> R >> x; flowers[L] += x; if (R + 1 <= n) { flowers[R + 1] -= x; } } for (int i = 1; i <= n; i++) { flowers[i] += flowers[i - 1]; } for (int i = 1; i <= n; i++) { prefixSum[i] = prefixSum[i - 1] + flowers[i]; } int queryL, queryR; cin >> queryL >> queryR; long long result = prefixSum[queryR] - prefixSum[queryL - 1]; cout << result << endl; return 0; } ``` 🌺 **算法解析** - 使用差分数组记录浇水操作，将区间更新转化为两个单点更新。 - 通过前缀和恢复每朵花的最终浇水次数。 - 利用前缀和数组快速计算任意区间浇水次数总和。 ⚙️ **复杂度分析** - 时间复杂度：O(n + q)，高效处理大规模数据。 - 空间复杂度：O(n)，仅需两个辅助数组。 💡 **使用示例** 输入： ``` 5 3 1 3 2 2 4 1 3 5 3 2 4 ``` 输出： ``` 16 ``` 解释： - 最终每朵花浇水次数：[2, 3, 6, 4, 3] - 区间[2,4]总和：3 + 6 + 4 = 13 ######[AI问答 | 434点数解答 | 2026-03-20 22:00:04]