算法(1) ——差分数组

前言

在一个具有多个元素的数组中，我们如果要频繁地去对数组中某个区间的元素进行修改，比如区间的所有元素都加5等等。那么我们最容易想到的就是暴力地去依次遍历加5，可能在遇到数组元素少的情况下，这样比较简单，但是遇到数据量大或是在一些实时的系统中可能就会变得很麻烦。所以，我们在这种情况下就可以使用——差分数组，来解决这个问题。

差分数组原理：

差分数组是与前缀和数组所对应的一种逆操作，类似于求导和积分，也就是说，对差分数组求前缀和，可以得到原数组，同样的，对前缀和数组求差分，也可以得到原数组。

其实差分数组本质上也是一个数组，我们暂且定义原数组为 d，差分数组 f 的大小和原来 d 数组长度一样，而且**f[i] = d[i] - d[i-1] (i≠0)**。

它的含义是什么？就是原来数组 i 位置上的元素和 i-1 位置上的元素作差，得到的值就是 f[i] 的值。

当我们希望对原数组的某一个区间 [l, r] 施加一个增量 x 时，差分数组d对应的变化是：d[l] +＝ｘ; d[r+1] －＝ x; 并且这种操作是可以叠加的。

例如：有数组d = [0,1,2,3,4,5]，对 d[2] 到 d[4] 之间的所有数加上3，变为d = [0,1,5,6,7,5]，那么差分数组也就从 f = [0,1,1,1,1,1] 变成了 f = [0,1,4,1,1,-2,]。

注意：差分数组元素从下标 1 开始存储

修改前：

index(下标)	0	1	2	3	4	5
d[i] (原数组)	0	1	2	3	4	5
f[i] (差分数组)	0	1	1	1	1	1

修改后：

index(下标)	1	2	3	4	5
d[i] (原数组)	1	2＋３＝５	3＋３＝６	4＋３＝７	5
f[i] (差分数组)	1	５－１＝４	６－５＝１	７－６＝１	５－７＝－２
差分数组前缀和(=原数组)	1+0=1	4+1+0=5	1+4+1+0=6	1+1+4+1+0=7	-2+1+1+4+1+0=5

由上面的表格可以知道，我们不用去遍历arr数组的[２，4]范围，然后再分别给每个值加上3，我们此时更改差分数组 f 即可。

显而易见，差分数组 f 在[2，4]范围内的值都不用改变，只需要改变差分数组位置 2 和位置 5 的值即可，即 f[2]= f[2 ]+ 3，而 f[5] = f[5] - 3，其余不变，为什么呢？因为差分数组的定义——f[i]=d[i]-d[i-1]

现在，我们如何根据差分数组 f 来推测 d 中某一个位置的值呢？

比如，此时，我们想知道 d[1] 的值，我们不能直接通过 d[1] 得到原来的值，因为在区间修改的操作中我们并没有修改d的值，因此我们必须从前往后遍历递推，由于f[1] = d[1] - d[0] (我们定义d[0]为0, f[0]为0)，那么d[1] = f[1] + d[0]，又由于f[1] = d[1] - d[0] = 1，那么d[1]=1+f[0]。以此类推，由于f[2]=d[2]-d[1]，所以d[2]=1+f[1]。

差分数组的定义

对于已知有n个元素的离线数列d，我们可以建立记录它每项与前一项差值的差分数组f，显然有：

$$
f[i]=\begin{cases} d[i]，(i=0);\ d[i]-d[i-1]， (1<=i<n);\end{cases}
$$

差分数组性质

(1)计算数列各项的值：原数列第i项的值是可以用差分数组的前i项的和计算的，即前缀和。
(2)计算数列每一项的前缀和：第i项的前缀和即为数列前i项的和，那么推导可知:
$$
SUM_x=\sum_{i=1}^x{d_x}={\sum_{i=1}^x}{\sum_{j=1}^x{f_j}}=\sum_{i=1}^x{(x-i+1)*f_i}
$$
即可用差分数组求出数列前缀和；

差分数组的用途

1）快速处理区间加减操作：

假如现在对数列中区间[L,R]上的数加上x，我们通过性质(1)可知道，第一个受影响的差分数组中的元素为 f[l],即令 f[l]+=x，那么后面数组元素在计算过程中都会加上x；最后一个受影响的差分数组中的元素为 f[r],所以令 f[r+1]-=x，即可保证不会影响到 r 以后数列元素的计算。这样我们不必对区间内每一个数进行处理，只需处理两个差分后的数即可；

2）询问区间和问题：

由性质(2)我们可以计算出数列各项的前缀和数组sum各项的值；那么显然，区间 [l,r] 的和即为ans=sum[r]-sum[l-1];

例题

题目描述

小明拥有n个彩灯，第 i个彩灯的初始亮度为ai。

小明将进行q次操作，每次操作可选择一段区间，并使区间内彩灯的亮度 +x（x可能为负数）。

求q次操作后每个彩灯的亮度（若彩灯亮度为负数则输出0）。

输入描述

第一行包含两个正整数 n, q，分别表示彩灯的数量和操作的次数。

第二行包含n个整数，表示彩灯的初始亮度。

接下来 q 行每行包含一个操作，格式如下：

l r x ，表示将区间 l ~ r 的彩灯的亮度 +x。

1 ≤ n， q ≤ 5 ✖ 10⁵，0 ≤ a_i ≤ 10⁹，1 ≤ l ≤ r ≤ n，-10⁹ ≤ x ≤ 10⁹

输出描述

输出共 1 行，包含 n 个整数，表示每个彩灯的亮度。

import java.util.Scanner;
/**
 * @author Cherish_779
 * @version 1.0
 * @Description     差分 --> 小明的彩灯
 * @date 2022/4/3 14:33
 */

/*
*   差分数组： f[i] = d[i] --> i = 0
*            f[i] = d[i] - d[i-1]  --> 1 <= i < n
*
*       (1)计算原数列各项的值：原数列第i项的值 是可以用差分数组的前i项的 和 计算的，即前缀和。
*
        1.快速处理区间加减操作：
        假如现在对数列中区间[L,R]上的数加上x，我们通过性质(1)知道，第一个受影响的差分数组中的元素为f[L],
        即令f[L]+=x，那么后面数列元素在计算过程中都会加上x；最后一个受影响的差分数组中的元素为f[R],
        所以令f[R+1]-=x，即可保证不会影响到R以后数列元素的计算。这样我们不必对区间内每一个数进行处理，
        只需处理两个差分后的数即可；

        2.询问区间和问题：
        由性质(2)我们可以计算出数列各项的前缀和数组sum各项的值；那么显然，
            区间[L,R]的和即为ans=sum[R]-sum[L-1];

*
* */
public class Test01 {
    public static void main(String[] args) {
        /*
        //超出时间限制 --> 暴力遍历

        final int N = (int)5e+05;
        int[] arr1 = new int[N];
        int[] arr2 = new int[N];

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();//彩灯的数量
        int q = scanner.nextInt();//操作的次数

        for(int i = 0; i < n; i++){
            arr1[i] = scanner.nextInt(); //n个整数，表示彩灯的初始亮度
        }

        for(int i = 0; i < q; i++){
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            long x = scanner.nextLong();

            for(int j = l-1; j < r; j++){
                arr2[j] += x;  //将每次操作后的亮度x赋给arr2数组
            }
        }

        for(int i = 0; i < n; i++){
            arr1[i] += arr2[i];
            if(arr1[i] <= 0){
                arr1[i] = 0;
            }
            System.out.print(arr1[i] + "\t");
        }

        */


     

        //优化 -->  差分数组
        int[] arr = new int[500010]; //原数组
        int[] f = new int[500010]; //差分数组

        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt(); //数组长度
        int q = scan.nextInt(); //操作次数

        for (int i = 1; i <= n; i++) {
            arr[i] = scan.nextInt(); //输入原数组元素值
        }

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


        for (int i = 0; i < q; i++) { //每次的操作
            int l = scan.nextInt();
            int r = scan.nextInt();
            int x = scan.nextInt();

            f[l] += x;
            f[r + 1] -= x;
        }

        for (int i = 1; i <= n; i++) {
            arr[i] = arr[i - 1] + f[i];
        }

        for (int i = 1; i <= n; i++) {
            if (arr[i] <= 0) {
                arr[i] = 0;
                System.out.print(arr[i] + "\t");
            } else {
                System.out.print(arr[i] + "\t");
            }
        }
    }
}