ToB企服应用市场:ToB评测及商务社交产业平台

标题: 蓝桥杯试题：小明的彩灯（差分 && 前缀和） [打印本页]

---

作者: 立聪堂德州十三局店    时间: 4 天前
标题: 蓝桥杯试题：小明的彩灯（差分 && 前缀和）
一、标题描述

小明拥有 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 个整数，表示每个彩灯的亮度。

二、代码实现

1. import java.util.Scanner;
2. // 1:无需package
3. // 2: 类名必须Main, 不可修改
5. public class Main {
6.     public static void main(String[] args) {
7.         Scanner scan = new Scanner(System.in);
8.         int N = scan.nextInt();
9.         int Q = scan.nextInt();
10.         int []n = new int[N];
11.         for(int i = 0 ; i < N ; i++ ){
12.           n[i] = scan.nextInt();
13.         }
14.         
15.         long[] diff = new long[N + 1];
16. //        diff[0] = n[0];
17. //        for(int i = 1 ; i < N ; i++){
18. //          diff[i] = n[i] - n[i-1];
19. //        }
21.         for(int i = 0 ; i < Q ; i++){
22.          int l = scan.nextInt() - 1;
23.          int r = scan.nextInt() - 1;
24.          int x = scan.nextInt();
25.          diff[l] += x;
26.          diff[r + 1] -= x;
27.         }
29.         for(int i = 1 ;i < N ; i++){   //diff被用来记录每次操作的亮度变化量
30.                                        //eg：diff[1] = diff[0] + diff[1] 表示n[1]总变化量
31.           diff[i] += diff[i-1];        //计算前缀和得到最终亮度的变化
32.         }
33.         
34.         for(int i = 0 ; i < N ; i++ ){
35.           long y = n[i] + diff[i];
36.           if(y < 0){
37.             y = 0;
38.           }
39.           System.out.print(y + " ");
40.         }
42.         scan.close();
43.     }
44. }

复制代码

  在代码中，
  `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`，只需执行：
  

1. D[l] += x;
2. 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企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4