算法小记 —— 差分数组

适用性

差分数组主要适用场景频繁对原始数组的某个区间的元素进行增减

原理

差分数组有点类似于前缀和，我们同样的需要构建一个数组用于存储数据，与前缀和不一样的是数组中的每一项求解的是num[i] - nums[i-1]

我们得到相应的差分数组后想要还原对应的原数组也是十分简单的，逻辑如下：

vector<int> result() {
    vector<int> nums;
    nums.push_back(diff[0]);
    for (int i = 1; i < diff.size(); ++i) {
    	nums.push_back(diff[i] + nums[i - 1]);
    }
    return nums;
}

当我们需要给区间nums[i..j]都加上或减少某个固定的值的时候，我们可以让diff[i] += val; diff[j+1] -= val或是diff[i] -= val; diff[j+1] += val

原理很简单，我们回想推导diff数组的过程可以发现，diff[i] + val意味着nums[i..]所有的元素都加了val，然后diff[j+1] - val意味着nums[j+1..]所有元素减去val，综合下来则是对nums[i..j]中的所有元素进行加了val

将其实现为一个类如下所示：

class Difference {
private:
    vector<int> diff;
public:
    Difference(vector<int> &nums) {
        diff.push_back(nums[0]);
        for (int i = 1; i < nums.size(); ++i) {
            diff.push_back(nums[i] - nums[i - 1]);
        }
    }

    void increment(int i, int j, int val) {
        diff[i] += val;
        // 还原数据
        if (j + 1 < diff.size()) {
            diff[j + 1] -= val;
        }
    }

    void decrement(int i, int j, int val) {
        diff[i] -= val;
        // 还原数据
        if (j + 1 < diff.size()) {
            diff[j + 1] += val;
        }
    }

    vector<int> result() {
        vector<int> res;
        res.push_back(diff[0]);
        for (int i = 1; i < diff.size(); ++i) {
            res.push_back(diff[i] + res[i - 1]);
        }
        return res;
    }
};

在increment、decrement函数中需要注意当j+1>=diff.length时，说明是对nums[i]及以后的整个数组都进⾏修改，那么就不需要再给diff数组减val了.

例子

1109. 航班预订统计 - 力扣（LeetCode）

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

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>> &bookings, int n) {
        vector<int> diff(n, 0), res(n, 0);
        for (auto booking: bookings) {
            diff[booking[0] - 1] += booking[2]; // 下标起始为 1
            if (booking[1] < n) {
                diff[booking[1]] -= booking[2];
            }
        }
        res[0] = diff[0];
        for (int i = 1; i < n; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
};