花园浇水次数统计：区间操作与查询算法详解

我来帮你分析这个问题。 ## 🧮 问题理解 - 有 `n` 朵花，编号从 1 到 n。 - 进行 `q` 轮浇水，每轮给区间 `[L, R]` 的每朵花增加 `x` 次浇水次数。 - 最后查询某个区间 `[a, b]` 的**每朵花浇水次数之和**（即区间内每朵花的浇水次数累加）。 ## 📊 数据范围 - n < 100 - 这意味着我们可以用简单的方法实现。 ## 💻 解决方案 ### 方法1：直接模拟 用一个数组记录每朵花的浇水次数，每次浇水操作直接遍历区间累加，最后查询时再遍历区间求和。 ```java import java.util.Scanner; public class FlowerWatering { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 输入花朵数量 int n = sc.nextInt(); int[] flowers = new int[n + 1]; // 下标从1开始 // 输入浇水轮数 int q = sc.nextInt(); // 处理浇水操作 for (int i = 0; i < q; i++) { int L = sc.nextInt(); int R = sc.nextInt(); int x = sc.nextInt(); // 给区间[L, R]的每朵花增加x次浇水 for (int j = L; j <= R; j++) { flowers[j] += x; } } // 输入查询区间 int a = sc.nextInt(); int b = sc.nextInt(); // 计算区间[a, b]的每朵花浇水次数之和 int sum = 0; for (int i = a; i <= b; i++) { sum += flowers[i]; } // 输出结果 System.out.println(sum); sc.close(); } } ``` ### 方法2：差分数组优化 如果浇水轮数很多，可以用差分数组优化浇水操作。 ```java import java.util.Scanner; public class FlowerWateringOptimized { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] diff = new int[n + 2]; // 差分数组，多开一位防止越界 int q = sc.nextInt(); // 使用差分处理浇水操作 for (int i = 0; i < q; i++) { int L = sc.nextInt(); int R = sc.nextInt(); int x = sc.nextInt(); diff[L] += x; diff[R + 1] -= x; } // 通过前缀和还原每朵花的浇水次数 int[] flowers = new int[n + 1]; for (int i = 1; i <= n; i++) { flowers[i] = flowers[i - 1] + diff[i]; } // 输入查询区间 int a = sc.nextInt(); int b = sc.nextInt(); // 计算区间和 int sum = 0; for (int i = a; i <= b; i++) { sum += flowers[i]; } System.out.println(sum); sc.close(); } } ``` ## ⚡ 复杂度分析 - **方法1**：每次浇水操作 O(R-L+1)，总复杂度 O(q × 区间长度)。n<100，完全可行。 - **方法2**：浇水操作 O(1)，还原数组 O(n)，查询 O(区间长度)。更高效。 ## 🎯 示例运行 输入： ``` 5 3 1 3 2 2 4 1 3 5 3 2 4 ``` 过程： 1. 浇水后每朵花次数：[2, 3, 6, 4, 3] 2. 查询区间[2,4]：3 + 6 + 4 = 13 输出： ``` 13 ``` ## 📝 注意事项 1. 数组下标从1开始，方便对应花朵编号。 2. 浇水次数可能累加得很大，使用`int`类型足够。 3. 如果n更大，需要使用方法2的差分优化。 ######[AI问答 | 955点数解答 | 2026-03-20 21:59:55]