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