差分数组.md

差分数组

0. 概念

区间更新问题除了最适用的线段树维护之后，还可以使用差分数组维护，顾名思义，差分数组元素就是原数组中两个元素之差，例如假设原数组为 arr=[7, 1, 5, 6, 3, 2, 4, 8]，那么查分数组就是 arr1=[0, -6, 4, 1, -3, -1, 2, 4]，arr1[0] 默认为 0，如下图：

差分数组是把原数组中后一个元素减前一个元素的差构成一个新的数组，作为辅助数组使用。具体来说：

// nums 是原数组，diff 是差分数组
diff[0] = nums[0];
diff[1] = nums[1] - nums[0];
diff[2] = nums[2] - nums[1];
...

nums[0] = diff[0];
nums[1] = diff[1] + nums[0] =  diff[0] + diff[1];
nums[2] = nums[1] + diff[2] =  diff[0] + diff[1] + diff[2];

1. 应用

一般来说，将原数组 nums 中 [0, 3] 的值都加2，我们需要遍历对应区间：

for (int i = 0; i < 4; ++ i) {
	nums[i] += 2;
}

但是使用差分数组我们就只需要更新端点就可以了：

diff[0] += 2;	// 0 往后（包括0）的所有值都加 2
diff[4] -= 2;	// 4 往后（包括4）的所有值都减 2

这样就省去了遍历操作，因为原数组的值可以通过差分数组两端的数求得。

2. 代码

以 732. 我的日程安排表 III 为例，我们维护有序的STL map，因为我们还原数组时候需要从头开始，是有顺序的，也就是使用 map 代替了数组，注意初始数组都为0，每次 book 都需要将区间内元素加1表示预定次数，然后求得区间元素最大值即为所求

class MyCalendarThree
{
public:
    MyCalendarThree()
    {
    }

    int book(int start, int end)
    {
        // 注意题目中是前开后闭区间
        diff[start]++; // start 开始的值都加 1
        diff[end]--;   // end 开始的值都减 1
        int res = 0;
        int cur = 0;
        for (auto &kv : diff)
        {
            cur += kv.second;    // 还原原数组，由于初始值都是0所以这里就只是加差分值
            res = max(res, cur); // 求预定次数的最大值
        }
        return res;
    }

private:
    map<int, int> diff; //差分数组
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(start,end);
 */

另外类似题还有：

• 729. 我的日程安排表 I

• 731. 我的日程安排表 II

3. 参考

• C++ 差分数组，注释详细
• 我的日程安排表 III【差分数组+线段树动态开点(带lazy)】