差分数组

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

对 nums 数组构造一个 diff 差分数组，**diff[i] 就是 nums[i] 和 nums[i-1] 之差**

1
2
3
4
5
6
7
int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}

1
2
3
4
5
6
7
int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

利用差分数组，我们可以高效地对原始数组的某个区间进行修改操作，而无需遍历整个区间。具体步骤如下：

  1. 对于要修改的区间 [start, end]，将差分数组的 diff[start] 增加 value，表示该区间起始位置的元素增加了 value。
  2. 将差分数组的 diff[end+1] 减去 value，表示该区间结束位置的下一个位置的元素减去了 value。

通过这样的操作，我们实际上是在修改差分数组中的两个位置，即对应于原始数组中修改区间起始位置和结束位置的下一个位置。

然后，我们可以根据差分数组重新构造原始数组。对差分数组进行前缀和操作，即 prefixSum[i] = prefixSum[i-1] + diff[i]，得到还原后的原始数组。

差分数组的主要应用场景是在需要频繁修改某个区间内元素的情况下，通过差分数组可以将修改操作的时间复杂度降低为 O(1)。它常用于解决一些与区间修改相关的问题，例如范围加法、区间翻转等。

前缀和

应用举例：

1
2
3
4
5
6
7
8
9
10
11
12
int[] scores; // 存储着所有同学的分数
// 试卷满分 100 分
int[] count = new int[100 + 1]
// 记录每个分数有几个同学
for (int score : scores)
    count[score]++
// 构造前缀和
for (int i = 1; i < count.length; i++)
    count[i] = count[i] + count[i-1];

// 利用 count 这个前缀和数组进行分数段查询

303. 区域和检索 - 数组不可变

304. 二维区域和检索 - 矩阵不可变

求前缀和数组的模板：（感觉混乱就画个图）

1
2
3
4
5
// 已知数组 nums
int[] preSum = new int[nums.length+1];
for(int i=1;i<preSum.length;i++){
	preSum[i] = preSum[i-1] + nums[i-1];
}