[[toc]]
差分数组
前面我们了解了前缀和
前缀和主要适用于原始数组不会被修改的情况下，频繁查询某个区间的累加和
差分数组主要适用于频繁对原始数组的某个区间的元素进行增减
比如我们给定一个数组nums
要求给区间nums[2..6]全部加1，再给nums[3..9]全部减3，再给nums[0..4]全部加2，最后问nums数组的值为多少？
常规做法就是每次在所给区间循环加上或者减去给定的值，时间复杂度为：O(m)，效率比较低。
这时就需要用到差分数组，我们先对nums数组构造一个diff差分数组，diff[i] = nums[i] - nums[i-1]
| nums |
8 |
2 |
6 |
3 |
1 |
| diff |
8 |
-6 |
4 |
-3 |
-2 |
1
2
3
4
5
6
| vector<int> diff(nums.size());
diff[0] = nums[0];
for(int i = 1; i < nums.size(); i++) {
diff[i] = nums[i] - nums[i - 1];
}
|
现在我们如何通过差分数组diff反推出元素数组nums？
我们可以看出nums[1]是前一个数的结果加上diff[i]得出的。
1
2
3
4
5
6
| vector<int> res(diff.size());
res[0] = diff[0];
for(int i = 1; i < diff.size(); i++) {
res[i] = res[i - 1] + diff[i];
}
|
那么现在假如我们对区间nums[1..3]的元素全部加3，我们应该如何计算呢？
我们只需要让diff[i] += 3,最后在让diff[j + 1] -= 3即可。
| nums |
8 |
5 |
9 |
6 |
1 |
| diff |
8 |
-3 |
4 |
-3 |
-5 |
原理很简单，回想前面diff数组反推nums
数组的过程，diff[i] += 3意味着给nums[i..]后所有的元素都加上了3，
然后diff[j + 1] -= 3又意味着给nums[j + 1..]后的所有元素减3，综合起来，就是相当于只对区间nums[i..j]中的所有元素都加3.
这样只需花费O(1)的时间修改diff数组，就相当于给nums的整个区间做了修改。
我们把差分数组抽象成一个类，包括increment和result方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class Difference {
private:
vector<int> diff;
public:
Difference(vector<int> nums) {
if(nums.size() > 0) {
diff.resize(nums.size());
diff[0] = nums[0];
for(int i = 1; i < nums.size(); i++) {
diff[i] = 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;
}
}
vector<int> result() {
vector<int> res(diff.size());
res[0] = diff[0];
for(int i = 1; i < diff.size(); i++) {
res[i] += res[i - 1] + diff[i];
}
return res;
}
};
|
算法实践
370. 区间加法
假设你有一个长度为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,-1]
[-2,0,3,5,3]
我们直接使用前面实现的类就可以解决：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
class Difference {
private:
vector<int> diff;
public:
Difference(vector<int> nums) {
if(nums.size() > 0) {
diff.resize(nums.size());
diff[0] = nums[0];
for(int i = 1; i < nums.size(); i++) {
diff[i] = 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;
}
}
vector<int> result() {
vector<int> res(diff.size());
res[0] = diff[0];
for(int i = 1; i < diff.size(); i++) {
res[i] += res[i - 1] + diff[i];
}
return res;
}
};
class Solution {
public:
vector<int> getModifiedArray(int length, vector<vector<int> > updates) {
vector<int> nums(length, 0);
Difference* df = new Difference(nums);
for(vector<int> update : updates) {
int i = update[0];
int j = update[1];
int val = update[2];
df->increment(i, j, val);
}
return df->result();
}
};
|