区间浇水问题：C++差分数组与前缀和优化实现

好的，这是一个典型的**区间修改 + 区间查询**的问题。 由于 n 和 q 可能达到接近 100，直接用暴力遍历每个区间进行累加是可以的，但如果数据量更大（比如 10^5）就会超时。 这里我会先给出一个**简单暴力法**（适合题目 n<100），再给出一个**差分 + 前缀和**的优化方法，适合更大的数据范围。 --- ## 🟢 暴力法（直接模拟） 直接开一个数组，对于每一轮浇水，遍历 L 到 R，累加 x。 ```cpp #include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> flowers(n + 1, 0); // 从1开始编号 for (int i = 0; i < q; i++) { int L, R, x; cin >> L >> R >> x; for (int j = L; j <= R; j++) { flowers[j] += x; } } int b, y; cin >> b >> y; long long sum = 0; for (int i = b; i <= y; i++) { sum += flowers[i]; } cout << sum << endl; return 0; } ``` **时间复杂度**：O(q * n) **空间复杂度**：O(n) --- ## 🔵 优化法：差分 + 前缀和（推荐） 差分数组 `diff[i]` 表示 `flowers[i] - flowers[i-1]` 的差值。 对于区间 [L, R] 增加 x，只需要： - 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, x; cin >> L >> R >> x; diff[L] += x; diff[R + 1] -= x; } // 还原每个花的浇水次数 vector<long long> flowers(n + 1, 0); for (int i = 1; i <= n; i++) { flowers[i] = flowers[i - 1] + diff[i]; } // 计算前缀和，便于区间查询 vector<long long> prefix(n + 1, 0); for (int i = 1; i <= n; i++) { prefix[i] = prefix[i - 1] + flowers[i]; } int b, y; cin >> b >> y; cout << prefix[y] - prefix[b - 1] << endl; return 0; } ``` **时间复杂度**：O(n + q) **空间复杂度**：O(n) --- ## 📌 开发注意要点 - 数组下标从1开始，避免边界判断混乱。 - 差分数组要多开一位，防止 R+1 越界。 - 如果 n 和 q 较大（比如 10^5），必须使用差分 + 前缀和，否则会超时。 - 使用 `long long` 存储浇水次数和，避免整数溢出。 - 对于多次区间查询，可以进一步使用线段树或树状数组，但本题只需一次查询，前缀和即可。 ######[AI问答 | 813点数解答 | 2026-06-21 19:35:43]