蓝桥杯冲刺：一维差分

系列文章目录

蓝桥杯系列：一维差分

前言

    前段时间我们讲了一维前缀和，这次我们来讲讲一维差分，就是跟一维前缀和是两个类似的概念，来快速处理区间加减的问题，下面我们来详细的讲解一下

一、一维差分：

            差分数组是一种简单而高效的数据结构，常用于快速处理区间加减的问题。

   对于一个长度为n的数组a，我们构造一个差分数组b，其定义为：

                  b[i] = a[i] - a[i-1],对于i>=2,b[1] = a[1];

           从差分数组还原原数组：

        通过对差分数组求前缀和可以还原出原数组：

                               a[i]=k=0∑i​d[k]

       差分数组的意义：

差分数组中的每个元素b[i]表示原数组中a[i]相对于a[i-1]的变化量。

二、差分的性质：

1. 原数组求差分：

   从原数组构造差分数组时，每次仅需要O(n)。

2.差分数组求前缀和:

   从差分数组恢复原数组，每次查询或还原数组均为O(n)。

3.快速区间修改：

    通过调整差分数组可以高效完成原数组的区间操作。

         对区间[l,r]的每个元素加上一个值d,只需:

                     b[l] += d，         b[r+1] -= d.

         在完成所有修改后，通过对差分数组求前缀和即可得到最终的结果数组。

     画图表示：

差分和前缀和的关系：

 原数组求前缀和 = 前缀和数组

 差分数组求前缀和=原数组

 前缀和数组求差分=原数组

 原数组求差分=差分数组

三、一维差分代码实现：

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = 1;
        while (T > 0) {
            solve(scan);
            T--;
        }
        scan.close();
    }

    public static void solve(Scanner scan) {
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[] arr = new int[n + 2];  // 原数组
        int[] b = new int[n + 2];  // 差分数组
        arr[0] = 0;
        b[0] = 0;

        // 读取原数组
        for (int i = 1; i <= n; i++) {
            arr[i] = scan.nextInt();
        }

        // 构建差分数组
        for (int i = 1; i <= n; i++) {
            b[i] = arr[i] - arr[i - 1];
        }


        // 区间更新
        while (m > 0) {
            int l = scan.nextInt();
            int r = scan.nextInt();
            int d = scan.nextInt();
            b[l] += d;
            b[r + 1] -= d;
            m--;
        }

        // 恢复原数组
        for (int i = 1; i <= n; i++) {
            b[i] = b[i] + b[i - 1];
        }

        // 输出恢复后的数组
        for (int i = 1; i <= n; i++) {
            System.out.print(b[i] + " ");
        }
    }
}

四、典型真题（利用一维差分来实现）

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();  // 读取n
        int[] arr = new int[n + 1];  // 创建数组，大小为n+1
        
        // 输入数组arr
        for (int i = 1; i <= n; i++) {
            arr[i] = scan.nextInt();  // 读取每个元素
        }
        
        // 创建b数组
        int[] b = new int[n + 1];
        b[1] = arr[1];  // b[1]等于arr[1]
        
        // 计算b数组的差值
        for (int i = 2; i <= n; i++) {
            b[i] = arr[i] - arr[i - 1];
        }
        
        // 计算结果
        long ans = b[1] - 1;
        for (int i = 2; i <= n; i++) {
            if (b[i] > 0) {
                ans += b[i];  // 如果b[i]大于0，加到答案上
            }
        }
        
        // 输出结果
        System.out.println(ans);
        
        scan.close();  // 关闭扫描器
    }
}

    这里面我们要注意的是就是不管是什么竞赛都要严格按样例进行输入输出，要不就是逻辑对的样例也是过不去的，所以一定要按照样例进行输入输出。

    这里面为什么只需要累计正差分呢？

假设原数组为 a = [a₁, a₂, ..., aₙ]，目标是所有元素变为1。

• ​​差分数组​​ d[i] = a[i] - a[i-1]（假设 a[0] = 0）。
• ​​正差分​​（d[i] > 0）：表示当前元素比前一个元素多出的“层数”。这些层数必须通过​​新增操作​​覆盖。
• ​​负差分​​（d[i] ≤ 0）：表示当前元素比前一个元素低或相等。这些层数已经被之前的操作覆盖，无需额外处理。

​​例子​​：

• 数组 [3, 2, 2] 的差分数组为 d = [3, -1, 0]。
  • d[1] = 3（必须覆盖的层数）。
  • d[2] = -1（已被之前的操作覆盖，无需新增）。
  • d[3] = 0（同样被覆盖）。

        这里面为什么负差分会包括进去呢？

因为每次操作可以覆盖一个区间。

• ​​负差分的位置​​（如 d[i] < 0）：表示当前元素比前一个元素低，之前的操作已经覆盖了它的减少需求。
• ​​操作示例​​：
  • 原数组 [3, 2, 2]，需要减少到 [1, 1, 1]。
  • 操作1：对整个数组减1 → [2, 1, 1]。
  • 操作2：仅对第一个元素减1 → [1, 1, 1]。
  • ​​负数差分（如 d[2] = -1）​​：在操作1中已经被覆盖，无需额外处理。

最后的调整（减1）是为什么？​​

• ​​差分数组的初始值​​：d[1] = a[1] - a[0] = a[1] - 0 = a[1]。
• ​​实际需求​​：第一个元素只需减少到1，而不是从0开始。因此，d[1] 中多计算了从0到1的冗余层数，需减去1。

​​例子​​：

• 数组 [3, 2, 2] 的差分和 sum(d) = 3 + (-1) + 0 = 2，但实际应为 3 - 1 = 2。
• ​​调整后​​：3（累加正差分） - 1（冗余层数） = 2，与实际操作次数一致。

• 正差分​​：必须通过新增操作覆盖。
• ​​负差分​​：已被之前的操作覆盖，无需处理。
• ​​减1调整​​：修正差分初始值的冗余计算。

总结

   一维差分和前缀和都很重要，都是可以对区间进行快速的操作，所以我们需要尽量掌握，接下来会持续更新算法的。