蓝桥杯试题：小明的彩灯（差分前缀和）

一、题目描述

小明拥有 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` 的代码片段。