差分数组实现区间快速加法统计浇水次数

我们可用差分数组来高效解决这个问题。差分数组可以在 O(1) 时间内完成区间加法，最后通过前缀和还原每朵花的浇水次数。 ### ✅ 解题步骤与示例代码 1. **初始化一个长度为 n+2 的差分数组 diff**，全部为 0。多出的长度用于处理区间右端点后的减法。 2. **对每一轮浇水区间 [L, R]**： - diff[L] += 1 - diff[R+1] -= 1 表示区间 [L, R] 内所有花被浇水一次。 3. **计算前缀和**： 遍历 i 从 1 到 n，sum += diff[i]，此时 sum 即为第 i 朵花的浇水次数。 4. **输出结果**，数字之间用空格分隔。 ### 💻 C语言代码实现 ```c #include <stdio.h> int main() { int n, q; scanf("%d %d", &n, &q); int diff[102] = {0}; // n < 100，多开一点空间防止越界 for (int i = 0; i < q; i++) { int L, R; scanf("%d %d", &L, &R); diff[L] += 1; diff[R + 1] -= 1; } int sum = 0; for (int i = 1; i <= n; i++) { sum += diff[i]; printf("%d", sum); if (i < n) { printf(" "); } } printf("\n"); return 0; } ``` ### 📌 关键要点 - **差分思想**：区间加操作变为两点修改，极大降低时间复杂度（O(n+q)）。 - **边界处理**：差分数组下标从 1 开始，R+1 位置减一，确保只影响 [L,R] 区间。 - **数组长度**：因为 n < 100，设置长度为 102 足够安全。 ######[AI问答 | 460点数解答 | 2026-06-21 19:23:44]