差分数组

问题背景

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

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

因此,今天的主角就出现了——差分数组

差分数组原理

比如我们现在有一个数组d,d={0,2,5,4,9,7,10,0}

d[i]025497100

那么差分数组是什么呢?

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

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

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

d[i]025497100
f[i]023-15-23-10

那么构造了这么个玩意有什么用呢?难道是来浪费宝贵的内存空间的?嗯,确实是来浪费宝贵的内存了,但是却换了时间上的高效。

现在我们有这么一个区间修改操作,即在区间1~4上,所有的数值都加上3.

d[i]02+35+34+39+37100
f[i]02+33-15-2-33-10

由上面的表格可以知道,我们不要傻傻地遍历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;
    }
}
03-05 22:12