算法之路-------差分数组-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法之路-------差分数组。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

差分数组的由来

针对数组中连续的大量数据进行修改的问题，如果我们对每个数据都进行依次修改，对于一些少量的数据的修改（例如：1~100这些的），修改的时候我们发现速度貌似还是很快的，但是一旦修改的连续数组中的数量上万了，那么修改的速率就明显下降了。

所以：针对这样的情况，就出现了差分数组。

差分数组的具体使用

1.差分数组的概念：

①差分数组：其实也就是一个额外的数组（说白了，就是为了挽回时间效率而利用空间去开辟一个数组帮我们更好的去管理一些数据），这个数组是为要改动的目标数组进行数据管理的。

②差分数组与要管理数组的关系：

假设要管理的数据为a，差分数组为d。对于不同的位置为i，那么对于差分数组而言，他每个位置的数为：d[i] = a[i] - a[i-1]。（d与a对应的每个位置的数据关系为：d与a对应位置的数据等于a当前位置减去a当前位置的上一个位置）

2.差分数据的使用方法：

①：首先，我们看下面一个例子：
假设a数组如下：
算法之路-------差分数组
注意：方格里面的是数组存放的数据，而上面的红色数字是对应的下标。

②：然后我们由差分数组概念得到的公式，计算数组a对应的差分数组d如下：
算法之路-------差分数组

然后我们按照1下标的计算，就可以将数组a的差分数组b计算出来，如图上。

3.差分数组的用法：

①：还是上面的例子，假设我们将数组a中从下标1到下标6的数字都要修改一遍，此时如果我们将数组a进行遍历，然后对对应的位置进行修改，这样的话会有点浪费时间，但是有了差分数组的帮助，我们可以可以轻而易举的做到。

②：对于①中要修改的区域（假设我们要将该区域的所有数+1），我们只需将差分数组中下标为1的数+1，和对应下标为7（6+1）的数-1。
所得的情况如下图：

算法之路-------差分数组

修改后如上图所示，修改后我们查看差分数组，我们发现，对于数组a修改了6个位置，而对应的数组d只修改2个位置就可以解决了（所以，我们不禁联想到，如果数组a是一个长达上千的数组，此时要修改的位置数以百计，而我们使用差分数组只需修改2个位置就可以结束战斗了，那这样是不是有点子划算）。

为什么会这样呢？

答：因为对于差分数组而言，他的每个数是对应数组该位置的数减去前一个数的差，所以我们对于同时做相同的修改数组的连续的数时，对应差分数组这个修改区间的数不需要修改，因为大家都做了相同的改变，所以差是相同的，但是对于边界要进行修改。

①：对于前沿（就是开始修改的位置），因为在原数组中该位置的数修改了，但是该位置前一个数没有修改，并且差分数组的值是原数组中该位置上的值减去前一个数字，所以差分数组这个位置上的值就等于原差分数组的值+要修改的值（带符号）。

②：对于后沿（就是修改的结束位置的下一位），因为对于该位置，原数组没有修改值，但是他前一个数字修改了，所以对于差分数组的该位置，应该是原差分数组的值-要修改的值（带符号）。

4.如何利用差分数组的值去得到原数组的值？

①我们知道对于差分数组和原数组的公式如下（a为原数组，d为差分数组）：

d[i] = a[i] - a[i-1]
d[0] = a[0]

从以上的我们可推出，对于每一个a上的对应位置上的数字，我们必须通过累加的形式完成。

拿上面的例子进行举例如下：
算法之路-------差分数组

假设我们要从差分数组d中推出下标为3的原数组a的值为多少，直接从差分数组从下标为0的数加到下标为3的下标即可得到，如上图：3+5+（-5）+（-8）= 11，也就是原数组a中下标为3的数。

②：所以有一下的累加公式，为从差分数组推出原数组：

算法之路-------差分数组
这里其实就是一个累加公式。
其中：sumx为前x项和

具体题目

例如：
力扣题目：731. 我的日程安排表 II
1.题目描述
算法之路-------差分数组
对于这道题，我们发现数据量非常大，所以想到了差分数组的方法。

2.解题思路：

因为对于一个时间段，这个时间段最多只能被选择两次，那么我们完全可以将这个数组设置出来，然后对区间段的值进行加1即可，有了这样的思想，由于数据量实在太大了，所以使用差分数组是非常合适的。

使用map用来保存每个时间段的起始位置和结束位置。（注意用底层为洪红黑树的map表，因为红黑树的map表会进行排序，非常利于我们进行操作）
然后将需要加入的区间加入，加入的时候因为要对区间的数据进行+1，所以对起始位置进行+1，对末尾位置进行-1。（由于此题是左开右闭，所以直接对末尾对应的位置进行-1即可）
然后对map表进行遍历，维护一个数字，用它来统计上面这个数据加进去后，会不出现有某个区间的值会大于2（预约的数量是3）。如果大于，那么该位置就不能加入，直接删除；如果小于，那么就加入。

为什么第三步遍历的时候就能正确的去进行是否可以进行插入的判断呢？

答：这就是我们使用红黑树为底层的map表的作用了，因为对于红黑树而言，他对加入的数据会进行排序，所以加入的数据在遍历的时候一定是从头到尾开始遍历的。而对于一个时间段，开始位置进行+1，而末尾位置进行-1，那么如果在一段区间内，维护的哪个变量变为3了，就证明在该区间内，遇见的开始位置比末尾位置大3，就证明刚才加入的这个区间会出现重复的情况，所以必须删除。

3.解答代码如下：

class MyCalendarTwo {
public:
    map<int,int> map;    //map表
    MyCalendarTwo() {}
    
    bool book(int start, int end) 
    {
        map[start]++;          //起始位置+1
        map[end]--;            //末尾位置-1
        int countlap = 0;      //维护预约计数变量从0开始

        for(auto& [l,r] : map)
        {
            countlap += r;     //因为map是排序过的，直接从第一个位置开始遍历即可
            if(countlap > 2)   //若有区间预约次数大于2了，那么这段时间应该被删除
            {
                map[start]--;
                map[end]++;
                return false;
            }
        }
        return true;
    }
};