什么是差分数组

其实差分数组和前缀和数组有点相似
前缀和主要适用于原始数组不会被修改的情况下，需要频繁查询某个区间的累计和

preSum[i]就是nums[0…i-1]所有元素的累加和
若求nums[i…j]的累加和，则计算preSum[j+1]-preSum[i]即可

差分数组主要适用于频繁对原始数组的某个区间的元素进行增减（即原数组需要频繁改变）

diff[0]=nums[0]
diff[i]就是nums[i]-nums[i-1]
对nums[i…j]的元素加3，只需要先让diff[i]+=3，然后让diff[j+1]-=3即可
diff[i]+=3相当于给nums[i…]的元素都加了3
diff[j+1]-=3相当于对nums[j+1]的元素都减了3
这两步合起来就是对nums[i…j]的元素加3

工具类

// 差分数组工具类
class Difference {// 差分数组private int[] diff;/* 输入一个初始数组，区间操作将在这个数组上进行 */public Difference(int[] nums) {assert nums.length > 0;diff = new int[nums.length];// 根据初始数组构造差分数组diff[0] = nums[0];for (int i = 1; i < nums.length; i++) {diff[i] = nums[i] - nums[i - 1];}}/* 给闭区间 [i, j] 增加 val（可以是负数）*/public void increment(int i, int j, int val) {diff[i] += val;if (j + 1 < diff.length) {diff[j + 1] -= val;}}/* 返回结果数组 */public int[] result() {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];}return res;}
}