蓝桥杯-小明的彩灯(Java-差分)
问题描述：
差分数组
1. 什么是差分数组？
差分数组 c 是原数组 a 的“差值表示”，其定义如下：
c[0] = a[0]c[i] = a[i] - a[i-1]（i ≥ 1）
差分数组记录了相邻元素的差值。例如，原数组 a = [1, 3, 5, 2] 对应的差分数组为 c = [1, 2, 2, -3]。
2. 差分数组的优势
通过差分数组，可以将区间操作转换为两次单点操作：
- 若要将区间
[l, r]的所有元素增加k，只需执行：c[l] += kc[r+1] -= k
这一操作的时间复杂度为O(1)，彻底避免了遍历区间。
3. 还原原数组
对差分数组进行前缀和运算即可还原原数组：
a[i] = c[0] + c[1] + ... + c[i]
前缀和的本质是逐步累加差分值，恢复出原数组的实际数值。
解题思路详解
步骤1：构建差分数组
- 初始化差分数组
c，长度为n+1（多一位用于处理右边界）。 - 根据原数组
a的相邻差值填充c，确保c[i] = a[i] - a[i-1]。
步骤2：处理区间操作
对于每个操作 [l, r, k]：
- 将
c[l] += k，表示从l开始的所有元素增加k。 - 将
c[r+1] -= k，表示在r+1处抵消多余的k，保证操作仅作用于[l, r]。
步骤3：还原修改后的数组
通过前缀和还原最终的数组：
- 从
c[1]开始，依次累加c[i] += c[i-1]，最终c[0...n-1]即为修改后的原数组。
代码：
public static void main(String[] args) {//通过原数组计算 差分 数组//再通过计算出的 差分 数组做 数据操作，例如（要将[l,r]区间所有数组+1）就将c[l]+1 c[r+1]-1//对差分数组，做前缀和操作得到原数组//有一个坑，虽然数据都是在int范围内，但是会涉及到相加操作，可能会超出int范围，所以我们的差分数组应该设置为longScanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] a = new int[n];//在创建差分数组的时候长度要设置为a.length + 1这是很有必要的,防止数组越界 这个边界操作(c[r + 1] -= 1;)long[] c = new long[n + 1];a[0] = sc.nextInt();//初始化差分数组c[0] = a[0];for (int i = 1; i < n; i++) {a[i] = sc.nextInt();c[i] = a[i] - a[i - 1];}
// System.out.println("原数组a:" + Arrays.toString(a));
// System.out.println("差分数组c:" + Arrays.toString(c));//要将[l,r]区间所有数组+cfor (int i = 0; i < m; i++) {int l = sc.nextInt();int r = sc.nextInt();int sum = sc.nextInt();c[l - 1] += sum;c[r] -= sum;}for (int i = 1; i < n; i++) {//这里复原的原理其实很简单// 例如对 1 2 3 4 5的[2,4]区间做+1操作，// 由于差分数组记录的是第i个数比第i-1个数大多少，之前i比i-1大1，+1操作之后，就是i比i-1大2了，// 但是由于我们要求在到[l,r]区间，所以r之后的差分就得还原 所以再做一个-1操作还原// 所以还原的时候，就能得到题目要求的数组了c[i] += c[i - 1];}for (int i = 0; i < n; i++) {if (c[i] < 0) {System.out.print(0 + " ");} elseSystem.out.print(c[i] + " ");}}