[差分阵列] 还不了解差分阵列？蓝桥杯算法模板问题 小明的彩灯解析
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=0
index
array[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(); } }
3.3 实现结果
上一篇： 使用 CSS 变量实现炫酷的悬停效果