差分数组

问题背景

如果给你一个蕴含 5000 万个元素的数组，而后会有频繁区间批改操作，那什么是频繁的区间批改操作呢？比方让第 1 个数到第 1000 万个数每个数都加上 1，而且这种操作时频繁的。

此时你应该怎么做？很容易想到的是，从第 1 个数开始遍历，始终遍历到第 1000 万个数，而后每个数都加上 1，如果这种操作很频繁的话，那这种暴力的办法在一些实时的零碎中可能就拉跨了。

因而，明天的配角就呈现了——差分数组。

差分数组原理

比方咱们当初有一个数组 d，d={0,2,5,4,9,7,10,0}

那么差分数组是什么呢？

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

它的含意是什么？就是原来数组 i 地位上的元素和 i - 1 地位上的元素作差，失去的值就是 d[i]的值。

所以，例子中的 arr 数组其对应的差分数组值如下图所示。

那么结构了这么个玩意有什么用呢？难道是来节约贵重的内存空间的？嗯，的确是来节约贵重的内存了，然而却换了工夫上的高效。

当初咱们有这么一个区间批改操作，即在区间 1~4 上，所有的数值都加上 3.

由下面的表格能够晓得，咱们不要傻傻地遍历 arr 数组的 [1，4] 范畴，而后再别离给每个值加上 3，咱们此时更改差分数组 d 即可。

不言而喻，差分数组 d 在 [2，4] 范畴内的值都不必扭转，只须要扭转差分数组地位 1 和地位 5 的值即可，即 f[1]=f[1]+3，而 f[5]=f[5]-3，其余不变，为什么呢？因为差分数组的定义——f[i]=d[i]-d[i-1]

当初，咱们如何依据差分数组 f 来揣测 d 中某一个地位的值呢？

比方，此时，咱们想晓得 d[1]的值，咱们不能间接通过 d[1]失去原来的值，因为在区间批改的操作中咱们并没有批改 d 的值，因而咱们必须从前往后遍历递推，因为 f[0]=d[0]-0(咱们定义 d[0]的前一个数为 0)，那么 d[0]=f[0]+0，又因为 f[1]=d[1]-d[0]=5，那么 d[1]=5+f[0]。以此类推，因为 f[2]=d[2]-d[1]，所以 d[2]=3+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];

差分数组用处利用

1. 题目

leetcode 1109. 航班预订统计

2. 解法

class Solution {public int[] corpFlightBookings(int[][] bookings, int n) {int[] nums = new int[n];
        for (int[] booking : bookings) {nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) {nums[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; i++) {nums[i] += nums[i - 1];
        }
        return nums;
    }
}