【差分数组】还不懂差分数组？蓝桥杯算法模板题小明的彩灯解析_java

Hi~大家好，我是大黄😎
本文对差分数组和小明的彩灯例题进行了讲解，如有不足之处欢迎评论区讨论~

文章目录

1.算法背景
2.差分数组
- 2.1 什么是差分数组？
- 2.2 差分数组的性质
3 例题——小明的彩灯
- 3.1 题目分析
- 3.2 参考代码（Java）
- 3.3 实现结果

1.算法背景

✈️试想一下，你有一个长度为100万的数组，这时候，你需要修改索引区间[1，100000]的值，我们很容易想到通过循环遍历数组来修改值。但是如果这种 *** 作是频繁的呢？你就需要频繁的遍历数组进行修改，而这个修改区间又比较大，因此，时间复杂度极高。为了使这种 *** 作更加高效，差分数组便出现了。

2.差分数组 2.1 什么是差分数组？

🐜我们给定一个数组nums = [1, 2, 3, 4, 5, 6]，为了便于计算，我们从索引1处开始赋值，索引0处默认为0。此时nums = [0, 1, 2, 3, 4, 5, 6]。
记nums的差分数组为array，则有array[ i ] = nums[ i ] - nums [ i-1 ]，求得差分数组array = [0, 1, 1, 1, 1, 1, 1]。

2.2 差分数组的性质

🥇对差分数组求前缀和即可得到原来的数组
对于上述数组，有nums[1] = array[0] + array[1];nums[2] = array[0] + array[1] + array[2];即有：

🌟nums[ index ] = ∑ i = 0 i n d e x a r r a y [ i ] \sum_{i=0}^{index} array[ i ] ∑i=0indexarray[i]

🥈若需要将原数组区间[l, r]的数字＋X，则修改后的数组的新差分数组满足array_1[l] += X; array_1[r+1] -= X;其余的差分数组值保持不变

3 例题——小明的彩灯

🍎题目链接：小明的彩灯
超链接若异常请手动复制访问：https://www.lanqiao.cn/problems/1276/learning/

【题目描述】
小明拥有 N个彩灯，第 i个彩灯的初始亮度为 a_i 小明将进行 Q次 *** 作，每次 *** 作可选择一段区间，并使区间内彩灯的亮度+x（x 可能为负数）。求 Q次 *** 作后每个彩灯的亮度（若彩灯亮度为负数则输出 0）。
【输入描述】
第一行包含两个正整数 N，Q，分别表示彩灯的数量和 *** 作的次数。
第二行包含 N 个整数，表示彩灯的初始亮度。
接下来 Q 行每行包含一个 *** 作，格式如下：
l r x，表示将区间 l∼r 的彩灯的亮度 +x。
【输出描述】
输出共 1 行，包含 N 个整数，表示每个彩灯的亮度。
【输入样例】
5 3
2 2 2 1 5
1 3 3
4 5 5
1 1 -100
【输出样例】
0 5 5 6 10

3.1 题目分析

定义array为nums的差分数组，将对nums数组的 *** 作转化为对array数组的 *** 作，后将前缀和记录到res数组中保存结果（注意灯的亮度不能小于0），最终输出结果即可。

3.2 参考代码（Java）

import java.util.Scanner;

public class test17 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();  // 数字数
        int Q = in.nextInt();  //  *** 作次数
        int[] nums = new int[N+1];  // 数字输入
        int[] array = new int[N+2]; // 差分数组
        int[] res = new int[N+1];  // 记录结果
        for (int i = 1; i <= N; i++) {
            nums[i] = in.nextInt();
        }
        for (int i = 1; i <= N; i++) {
            array[i] = nums[i] - nums[i-1];
        }
        //  *** 作
        while (Q-- != 0){
            int l = in.nextInt();  // 左区间
            int r = in.nextInt();  // 右区间
            int x = in.nextInt();
            array[l] += x;
            array[r+1] -= x;
        }
        // 计数前缀和
        res[1] = array[1];
        for (int i = 2; i <= N ; i++) {
            res[i] = res[i-1] + array[i];
        }
        // 打印结果 控制输出格式
        for (int i = 1; i <= N; i++) {
            if(res[i] >= 0){
                if(i == N)
                    System.out.print(res[i]);
                else
                    System.out.print(res[i] + " ");
            }else {
                if(i == N)
                    System.out.print("0");
                else
                    System.out.print("0 ");
            }
        }
        in.close();
    }
}