算法学习-差分数组

差分数组

• 参考教程：https://wansuanfa.com/index.php/589
• leetcode题目：1109. 航班预订统计

问题描述

给定一个数组，需要频繁地对某个区间内的元素做加减操作，并获取最后的操作结果。常规做法是每次都遍历整个区间然后修改区间内的元素，但是元素的访问需要时间、频繁访问元素会减慢程序的运行时间。因此，可以使用差分数组来进行优化。

一维差分数组定义

一维差分数组 d[n] 定义为原始数组 nums 相邻元素之间的差，即d[i]=nums[i]-nums[i-1]，其中d[0]=nums[0]。这样原数组就是差分数组的前缀和

由此，我们可以改进原来的区间操作，如对区间[a,b]内每个元素加3，那么只需要在区间的两端进行操作即可，即

证明

假设nums1是修改后的数组，d1是修改后的差分数组，其中d1[a]=d[a]+3, d1[b+1]=d[b+1]-3.

hugo里面换行公式需要\\\\四个反斜杠

• 对于0\leq i \lt a, nums1[i] = \sum_{k=0}^i d1[k] = \sum_{k=0}^i d[k] = nums[i].
• 对于a\leq i \leq b,
  \begin{aligned} nums1[i] & = \sum_{k=0}^i d1[k] \\\\ & = \sum_{k=0}^{a-1}d[k] + \sum_{k=a+1}^{b}d[k] + d[a] + 3 \\\\ & = \sum_{k=0}^i d[k] + 3 \\\\ & = nums[i]+3 \end{aligned}
• 对于i \gt b,
  \begin{align} nums1[i] &= \sum_{k=0}^i d1[k]\\\\ &= \sum_{k=0}^{a-1}d[k] + \sum_{k=a+1}^{b}d[k] + \sum_{k=b+1}^{i}d[k] + d[a] + 3 + d[b] - 3\\\\ &= \sum_{k=0}^i d[k] + 3 - 3\\\\ &= nums[i]. \end{align}
  由此，可以证明只修改差分数组的两端即可以修改原数组的整个区间。

代码

class Solution {
public:
    vector<int> diff;
    vector<int> nums;

    void diffNums() {
        diff[0] = nums[0];
        for(int i = 1; i < nums.size(); ++i) {
            diff[i] = nums[i] - nums[i-1];
        }
    }

    void increment(int a, int b, int val) {
        diff[a] += val;
        if (b + 1 < diff.size())
            diff[b + 1] -= val;
    }

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

    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        nums.resize(n, 0);
        diff.resize(n, 0);
        diffNums();
        for (int i = 0; i < bookings.size(); ++i) {
            increment(bookings[i][0]-1, bookings[i][1]-1, bookings[i][2]);
        }
        result();
        return nums;
    }
};

拓展 - 二维差分数组

二维差分数组可以在一维差分数组的基础上进行拓展，视为一个平面，定义如下

那么相应地

假设以 (x1,y1) 为左上角， (x2,y2) 为右下角构成一个区间S，如果对这个区间内的每个元素增加val，只需要执行下面四步即可。

证明

同样假设num1和d1是修改后的数组和查分数组，以下分情况进行讨论

• 对于(m,n)满足m或n, 容易知道该范围内查分数组未发生变化，求解该范围内的数组不需要用到区间S内的差分数组，因此该范围内数组不受影响；
• 对于(m,n)\in S, 不妨设原数组num的元素均为a, 那么
  \begin{align} nums1[x1][y1] &= nums1[x1-1][y1] + nums1[x1][y1-1] - nums1[x1-1][y1-1] + d1[x1][y1]\\\\ &= nums[x1-1][y1] + nums[x1][y1-1] - nums[x1-1][y1-1] + d[x1][y1] + val\\\\ &= nums[x1][y1] + val; \end{align}
  对于S内的其他点，使用此递推公式同样可以推导出
  nums1[m,n] = nums[m][n]+val
• 对于(m,n)满足x1\leq m \leq x2且n\gt y2, 我们可以知道
  \begin{align} nums1[x1][y2+1] &= nums1[x1-1][y2+1] + nums1[x1][y2] - nums1[x1-1][y2] + d1[x1][y2+1]\\\\ &= nums[x1-1][y2+1] + nums[x1][y2] + val - nums[x1-1][y2] + d[x1][y2+1] - val\\\\ &= nums[x1][y2+1]; \end{align}
  对于其他(m,n)使用递推公式同样可以发现数组的值没有发生变化。
• 对于(m,n)满足m\gt x2且y1\leq n \leq y2, 可以使用类似上一种情况的方式推导发现数组数值未发生变化；
• 最后，对于(m,n)满足m\gt x2且n\gt y2，我们考虑
  \begin{align} nums1[x2+1][y2+1] &= nums1[x2][y2+1] + nums1[x2+1][y2] - nums1[x2][y2] + d1[x2+1][y2+1]\\\\ &= nums[x2][y2+1] + nums[x2+1][y2] - nums[x2][y2] - val + d[x2+1][y2+1] + val\\\\ss &= nums[x2+1][y2+1]; \end{align}
  对于该区域其他点可以类推。

由此，我们得到，差分数组定义以及更新方式满足条件。

代码（来自参考链接）

// Java代码，需要注意边界情况
private int[][] d;// 差分数组。
private int[][] a;// 原数组。

public TwoDiffNums(int[][] a) {
    this.a = a;
    int m = a.length;
    int n = a[0].length;
    d = new int[m][n];
    // 求差分数组。
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            add(i, j, i, j, a[i][j]);
}

public void add(int x1, int y1, int x2, int y2, int val) {
    d[x1][y1] += val;
    if (y2 + 1 < d[0].length)
        d[x1][y2 + 1] -= val;
    if (x2 + 1 < d.length)
        d[x2 + 1][y1] -= val;
    if (x2 + 1 < d.length && y2 + 1 < d[0].length)
        d[x2 + 1][y2 + 1] += val;
}

// 返回结果数组。
public int[][] result() {
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[0].length; j++) {
            int x1 = i > 0 ? a[i - 1][j] : 0;
            int x2 = j > 0 ? a[i][j - 1] : 0;
            int x3 = i > 0 && j > 0 ? a[i - 1][j - 1] : 0;
            a[i][j] = x1 + x2 - x3 + d[i][j];
        }
    }
    return a;
}