差分数组
- 参考教程：https://wansuanfa.com/index.php/589
- leetcode题目：1109. 航班预订统计
问题描述
给定一个数组，需要频繁地对某个区间内的元素做加减操作，并获取最后的操作结果。常规做法是每次都遍历整个区间然后修改区间内的元素，但是元素的访问需要时间、频繁访问元素会减慢程序的运行时间。因此，可以使用差分数组来进行优化。
一维差分数组定义
一维差分数组$ d[n] $定义为原始数组$ nums $相邻元素之间的差，即$d[i]=nums[i]-nums[i-1]$，其中$d[0]=nums[0]$。这样原数组就是差分数组的前缀和
$$ nums[i] = \sum_{k=0}^i d[k]. $$
由此，我们可以改进原来的区间操作，如对区间$[a,b]$内每个元素加3，那么只需要在区间的两端进行操作即可，即
$$ d[a] += 3, d[b+1] -= 3 $$
证明
假设$nums1$是修改后的数组，$d1$是修改后的差分数组，其中$d1[a]=d[a]+3, d1[b+1]=d[b+1]-3$.
- 对于$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{align} 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{align}. $$
对于$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;
}
};拓展 - 二维差分数组
二维差分数组可以在一维差分数组的基础上进行拓展，视为一个平面，定义如下
$$ d[i][j] = nums[i][j] - nums[i-1][j] - nums[i][j-1] + nums[i-1][j-1] $$
那么相应地
$$ nums[i][j] = nums[i-1][j] + nums[i][j-1] - nums[i-1][j-1] + d[i][j] $$
假设以 $(x1,y1)$ 为左上角， $(x2,y2)$ 为右下角构成一个区间$S$，如果对这个区间内的每个元素增加$val$，只需要执行下面四步即可。
$$ \begin{align} &d[x1][y1] += val \\ &d[x1][y2+1] -= val \\ &d[x2+1][y1] -= val \\ &d[x2+1][y2+1] += val \end{align} $$
证明
同样假设$num1$和$d1$是修改后的数组和查分数组，以下分情况进行讨论
- 对于$(m,n)$满足$m<x1$或$n<y1$, 容易知道该范围内查分数组未发生变化，求解该范围内的数组不需要用到区间$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\\ &= 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;
}
评论 (0)