一、题目描述
小明拥有 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[i] += diff[i-1]; }`
这一行代码的作用是 " 计算差分数组的前缀和 "，从而得到每个彩灯在所有操作之后的最终亮度变化量。
1.差分数组的基本概念
是一种用于高效处理区间更新的数据结构。假设你有一个原数组 `A`，差分数组 `D` 定义如下：
- `D[0] = A[0]`
- `D[i] = A[i] - 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[i]` 表示 `n[i]` 相对于 `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[i] += diff[i-1];
}
这一步是关键。通过计算差分数组的前缀和，`diff[i]` 最终表示原数组 `n[i]` 在所有操作之后的总变化量。具体来说：
- `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` 的瞬时变化量，而不是累积的总变化量。通过计算前缀和，你可以将所有在位置 `i` 之前的变化量累加起来，得到每个彩灯的最终亮度变化。
3.总结
- 差分数组用于高效地处理区间更新操作。
- 前缀和用于将差分数组转换回原数组的实际变化量。
- 在代码中，`for(int i = 1 ; i < N ; i++) { diff[i] += diff[i-1]; }` 这一行通过计算前缀和，将差分数组转换为每个彩灯的总亮度变化量，从而得到最终结果。
经过注释的diff数组代码
diff[0] = n[0];
for(int i = 1 ; i < N ; i++){
diff[i] = n[i] - n[i-1];
}
这段代码用于初始化差分数组 `diff`，使其表示原数组 `n` 的差分。
1.差分数组的正确使用方法
差分数组 `diff` 的主要用途是高效地处理区间更新操作。具体步骤如下：
1. 初始化差分数组：
- `diff[0] = n[0]`
- 对于 `i` 从 `1` 到 `N-1`，`diff[i] = n[i] - 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` 的代码片段。
