算法笔记——差分数组

​​点击阅读更多查看文章内容

差分数组

概念

所谓差分数组就是对数组的相邻元素求差保存到一个新的数组中，这个数组就是差分数组。
如下所示：

序号	0	1	2	3	4
原数组a	1	5	3	4	3
差分数组d	1	4	-2	1	-1

作用

用于频繁的区间修改
区间修改是对数组的一段区间同时加上或减去某一个数
对上面的数组我们执行如下操作：
1.对区间[0,3]中的每个元素加3
2.对区间[1,2]中的每个元素减2
我们不难想到可以通过遍历区间中的每个元素来实现，但是如果区间很大，执行的操作很多时，这种方法很容易超时。这时就需要用到差分数组。

我们观察当我们对区间[0,3]中的每个元素进行加3操作时，差分数组只有d[0]和d[4]会发生变化。

序号	0	1	2	3	4
原数组a	4	8	6	7	3
差分数组d	4	4	-2	1	-4

同理，对区间[1,2]执行减2操作时，只有d[1]和d[3]会发生变化。

序号	0	1	2	3	4
原数组a	4	6	4	7	3
差分数组d	4	2	-2	3	-4

这就是差分数组所有的性质：当对区间[i,j]进行加减操作时，差分数组d[i]进行相同的操作，d[j+1]进行相反的操作。
利用差分数组的这个性质，我们对数组任意长度的区间修改不再需要遍历每个元素而只需要修改差分数组两个元素的值即可。
当进行完所有的区间操作后，对差分数组求一个前缀和即可得到原数组。
因为d[i]=a[i]-a[i-1]，所以a[i]=a[i-1]+d[i]，并且有a[0]=d[0]，我们可以从前往后依次求出a[i]。

例题

LeetCode1109

参考代码

class Solution
{
public:
    vector<int> corpFlightBookings(vector<vector<int>> &bookings, int n)
    {
        vector<int> d(n, 0);
        for (int i = 0; i < bookings.size(); i++)
        {
            int fir = bookings[i][0] - 1;
            int last = bookings[i][1] - 1;
            int seats = bookings[i][2];
            d[fir] += seats;
            if(last+1<n)
                d[last + 1] -= seats;
        }
        for (int i = 1; i < n; i++)
        {
            d[i] += d[i - 1];
        }
        return d;
    }
};