差分数组

问题背景

如果给你一个蕴含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;    }}