算法基础算法

差分维护区间加法

字数统计: 1.2k字   |   阅读时长: 5分
, , ,

摘要: 本文通过详细拆解 leetcode 370 来理解差分的算法

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，在文章 【模板】前缀和与差分 中，我们串讲了前缀和的算法原理和代码模板，并且前缀和与差分的关系。

本文我们以力扣 370 为模板题，详细学习差分的算法，以及最典型的应用：用差分维护区间加, 查询最终单点值。最后我们用查分的算法解决力扣 1109。

$1 模板题

假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k 个更新的操作。

其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex … endIndex]（包括 startIndex 和 endIndex）增加 inc。

请你返回 k 次操作后的数组。

示例:
输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
输出: [-2,0,3,5,3]

解释:
初始状态:
[0,0,0,0,0]
进行了操作 [1,3,2] 后的状态:
[0,2,2,2,0]
进行了操作 [2,4,3] 后的状态:
[0,2,5,5,3]
进行了操作 [0,2,-2] 后的状态:
[-2,0,3,5,3]

算法: 差分

前缀和序列 $S_{0}, S_{1}, …, S_{n}$ 的差分序列 $a_{0}, a_{1}, …, a_{n-1}$ 就等于原序列，其中 $a_{i} = S_{i+1} - S_{i}$ 。

原序列 $a_{0}, a_{1}, …, a_{n-1}$ 的差分序列为 $b_{0}, b_{1}, …, b_{n-1}$ ，其中 $b_{0} = a_{0} - 0, b_{i} = a_{i} - a_{i-1}$ 。则对差分序列求前缀和序列，就得到原序列。

差分序列的好处是如果要对原序列的一个区间 [l, r] 上所有值加 val，原序列上要操作 r-l+1 次 (a[l .. r] + val)，在差分序列上只需要操作 2 次 (b[l] + val, b[r+1] - val)。

1
2
3
4
5
6
7
// [s..e] 增加 i
void update(int s, int e, int i)
{
    diff[s] += i;
    if(e + 1 < n)
        diff[e + 1] -= i;
}

如果这种区间操作需要很多次，最后的查询只有一次的话，即求一次前缀和。就非常适合在差分序列上操作。

1
2
3
4
vector<int> result(n);
result[0] = diff[0];
for(int i = 1; i < n; ++i)
    result[i] = result[i - 1] + diff[i];

如果查询有多次，那么每次查询都有求一次前缀和，即 result 要算多次。可以考虑将前缀和数组 result 改为带单点修改前缀和即树状数组来优化，参考 力扣307-线段树,树状数组。

代码(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> getModifiedArray(int length, vector<vector<int>>& updates) {
        int n = length;
        vector<int> diff(n);
        for(const vector<int>& update: updates)
        {
            int s = update[0], e = update[1], i = update[2];
            diff[s] += i;
            if(e + 1 < n)
                diff[e + 1] -= i;
        }
        vector<int> result(n);
        result[0] = diff[0];
        for(int i = 1; i < n; ++i)
        {
            result[i] = result[i - 1] + diff[i];
        }
        return result;
    }
};

$2 题目

这里有 n 个航班，它们分别从 1 到 n 进行编号。

我们这儿有一份航班预订表，表中第 i 条预订记录 bookings[i] = [first[i], last[i], seats[i]] 意味着我们在从 first[i] 到 last[i] 的每个航班上预订了 seats[i] 个座位。

请你返回一个长度为 n 的数组 answer，按航班编号顺序返回每个航班上预订的座位数。

提示：

1
2
3
4
5
1 <= n <= 2 * 1e4
1 <= bookings.length <= 2 * 1e4
bookings[i].length == 3
1 <= first[i] <= last[i] <= n
1 <= seats[i] <= 1e4

示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]

示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> nums(n + 1);
        vector<int> diff(n + 1); // diff[i] = nums[i + 1] - nums[i]
        for(vector<int> &record: bookings)
        {
            int i = record[0], j = record[1], k = record[2];
            diff[i - 1] += k;
            diff[j] -= k;
        }
        for(int i = 1; i <= n; ++i)
            nums[i] = nums[i - 1] + diff[i - 1];
        for(int i = 0; i < n; ++i)
            nums[i] = nums[i + 1];
        nums.pop_back();
        return nums;
    }
};
Share