一、标题描述
小明拥有 N 个彩灯，第 ii个彩灯的初始亮度为 ai。
小明将举行 Q次操纵，每次操纵可选择一段区间，并使区间内彩灯的亮度 +x（x 可能为负数）。
求 QQ次操纵后每个彩灯的亮度（若彩灯亮度为负数则输出 0）。
输入描述
第一行包含两个正整数 N，Q，分别表示彩灯的数量和操纵的次数。
第二行包含 N 个整数，表示彩灯的初始亮度。
接下来 Q 行每行包含一个操纵，格式如下：
l r x，表示将区间 l∼r的彩灯的亮度 +x。
1≤N,Q≤5×1051≤N,Q≤5×105，0≤ai≤1090≤ai≤109，1≤l≤r≤N1≤l≤r≤N，−109≤x≤109−109≤x≤109
输出描述
输出共 1行，包含 N 个整数，表示每个彩灯的亮度。
二、代码实现
- import java.util.Scanner;
- // 1:无需package
- // 2: 类名必须Main, 不可修改
- public class Main {
- public static void main(String[] args) {
- Scanner scan = new Scanner(System.in);
- int N = scan.nextInt();
- int Q = scan.nextInt();
- int []n = new int[N];
- for(int i = 0 ; i < N ; i++ ){
- n[i] = scan.nextInt();
- }
-
- long[] diff = new long[N + 1];
- // diff[0] = n[0];
- // for(int i = 1 ; i < N ; i++){
- // diff[i] = n[i] - n[i-1];
- // }
- for(int i = 0 ; i < Q ; i++){
- int l = scan.nextInt() - 1;
- int r = scan.nextInt() - 1;
- int x = scan.nextInt();
- diff[l] += x;
- diff[r + 1] -= x;
- }
- for(int i = 1 ;i < N ; i++){ //diff被用来记录每次操作的亮度变化量
- //eg：diff[1] = diff[0] + diff[1] 表示n[1]总变化量
- diff[i] += diff[i-1]; //计算前缀和得到最终亮度的变化
- }
-
- for(int i = 0 ; i < N ; i++ ){
- long y = n[i] + diff[i];
- if(y < 0){
- y = 0;
- }
- System.out.print(y + " ");
- }
- scan.close();
- }
- }
`for(int i = 1 ; i < N ; i++) { diff += diff[i-1]; }`
这一行代码的作用是 " 计算差分数组的前缀和 "，从而得到每个彩灯在全部操纵之后的最终亮度变化量。
1.差分数组的根本概念
是一种用于高效处置惩罚区间更新的数据布局。假设你有一个原数组 `A`，差分数组 `D` 界说如下：
- `D[0] = A[0]`
- `D = A - A[i-1]` （对于 `i > 0`）
通过差分数组，可以在 O(1) 的时间内对原数组的一个区间举行增减操纵。例如，要将区间 `[l, r]` 的每个元素增长 `x`，只需执行：
- D[l] += x;
- D[r + 1] -= x; // 如果 r + 1 在数组范围内
差分数组 `diff` 被用来记录每次操纵的亮度变化：
1. 初始化差分数组：
long[] diff = new long[N + 1];
这里 `diff` 的大小为 `N + 1`，其中 `diff[0]` 对应原数组的第一个元素，`diff` 表示 `n` 相对于 `n[i-1]` 的变化量。
2. 应用全部操纵到差分数组：
for(int i = 0 ; i < Q ; i++){
int l = scan.nextInt() - 1;
int r = scan.nextInt() - 1;
int x = scan.nextInt();
diff[l] += x;
if(r + 1 < N){
diff[r + 1] -= x;
}
}
这里，每次操纵将区间 `[l, r]` 的亮度增长 `x`，通过在 `diff[l]` 增长 `x` 并在 `diff[r + 1]` 减少 `x` 来实现。
3. 计算前缀和以得到最终的亮度变化：
for(int i = 1 ; i < N ; i++){
diff += diff[i-1];
}
这一步是关键。通过计算差分数组的前缀和，`diff` 最终表示原数组 `n` 在全部操纵之后的总变化量。具体来说：
- `diff[0]` 保持不变，表示 `n[0]` 的变化量。
- `diff[1] = diff[0] + diff[1]`，表示 `n[1]` 的总变化量。
- `diff[2] = diff[0] + diff[1] + diff[2]`，依此类推，直到 `diff[N-1]`。
2.为什么必要计算前缀和
假如不计算前缀和，`diff` 只表示在位置 `i` 的瞬时变化量，而不是累积的总变化量。通过计算前缀和，你可以将全部在位置 `i` 之前的变化量累加起来，得到每个彩灯的最终亮度变化。
3.总结
- 差分数组用于高效地处置惩罚区间更新操纵。
- 前缀和用于将差分数组转换回原数组的实际变化量。
- 在代码中，`for(int i = 1 ; i < N ; i++) { diff += diff[i-1]; }` 这一行通过计算前缀和，将差分数组转换为每个彩灯的总亮度变化量，从而得到最终结果。
颠末表明的diff数组代码
diff[0] = n[0];
for(int i = 1 ; i < N ; i++){
diff = n - n[i-1];
}
这段代码用于初始化差分数组 `diff`，使其表示原数组 `n` 的差分。
1.差分数组的精确使用方法
差分数组 `diff` 的重要用途是高效地处置惩罚区间更新操纵。具体步骤如下：
1. 初始化差分数组：
- `diff[0] = n[0]`
- 对于 `i` 从 `1` 到 `N-1`，`diff = n - n[i-1]`
2. 应用区间更新：
- 对于每次操纵 `(l, r, x)`，执行：
diff[l] += x;
if(r + 1 < N){
diff[r + 1] -= x;
}
3. 计算最终结果：
- 通过计算差分数组的前缀和，得到每个位置的最终变化量。
- 将变化量加到原数组 `n` 上，并根据标题要求处置惩罚负数情况。
2.为什么保留初始化代码会导致错误
假如保留了初始化差分数组的代码：
然后继承应用区间更新，这会导致以下标题：
1. 双重记录初始值：
- 初始化时，`diff[0]` 被设置为 `n[0]`，表示 `n[0]` 的初始值。
- 然后应用区间更新时，`diff[l] += x` 和 `diff[r + 1] -= x` 会在已经包含初始值的基础上再增长或减少 `x`，导致初始值被重复计算。
2. 错误的累积变化：
- 例如，假设初始数组 `n = [1, 2, 3]`，而且有一个操纵 `(0, 2, 5)`，即对全部灯增长 `5`。
- 精确的差分数组应该是 `[5, 5, 0, -5]`，表示：
- `diff[0] = 5` → `n[0] += 5` → `6`
- `diff[1] = 5` → `n[1] += 5` → `7`
- `diff[2] = 0` → `n[2] += 0` → `3`
- `diff[3] = -5` → `n[3] -= 5`（假如存在）
- 结果应为 `[6, 7, 3]`
- 假如保留初始化代码，`diff[0]` 已经是 `1`，再加上 `5` 变成 `6`，但后续的 `diff[1]` 也会基于 `n[1] = 2` 而不是新的 `7`，导致结果错误。
3.精确的做法
在处置惩罚差分数组时，通常有两种方法：
1. 仅使用差分数组举行更新，末了通过前缀和恢复原数组：
- 不必要初始化 `diff` 为 `n` 的值。
- 直接应用全部操纵到 `diff` 上。
- 末了通过前缀和计算每个位置的最终值。
2. 在初始化时设置差分数组，然后应用增量更新：
- 假如必要在初始值的基础上举行增量更新，确保在应用区间更新时精确处置惩罚。
仅使用差分数组举行更新，并通过前缀和恢复最终结果 是更轻便且不易出错的方法。因此，应该移除初始化 `diff` 为 `n` 的代码片断。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
