一维差分

对于数组 a，定义其差分数组（difference array）为

d[i] = \begin{cases} a[0], & \quad i = 0 \\ a[i] - a[i - 1], & \quad i \geq 1 \end{cases}

差分数组具有以下性质：

性质 1：从左到右累加 d 中的元素，可以得到数组 a。
性质 2：如下两个操作是等价的。
- 把 a 的子数组 $a[i],a[i+1],…,a[j]$ 都加上 $x$ 。
- 把 $d[i]$ 增加 $x$ ，把 $d[j+1]$ 减少 $x$ 。

观察性质 2，原本 $O(n)$ 的操作可以变为 $O(1)$ 的操作，然后通过性质 1 使用 $O(n)$ 的时间恢复数组 a。性质 2 也告诉我们差分数组是怎么影响原数组的。当 $d[i]$ 发生变动，如加 1，表示把 a 中下标 i 及后面的数都加上了 1。

本节例题 🟨 1094. 拼车 - 力扣（LeetCode）

int[] diff = new int[1003];
for(int[] q: questions){
	diff[q[1]]+=q[0]; // start
	diff[q[2]]-=q[0]; // end+1
}
int pre = 0;          // 前缀和
for(int i=0;i<=1000;i++){
	pre+=diff[i];
	// 通过前缀和还原原数组
}

相关题目：

🟩 2848. 与车相交的点 - 力扣（LeetCode）

如果差分数组的数据比较稀疏，或构建差分数组的长度过大，那么在实现差分数组时除了建立一个 Array 数组外，还可以使用 Map 替代数组记录下标和值的键值对。

Java 具体做法为，使用 TreeMap 或使用普通 Map，再对 key 做一次排序。

Map<Integer,Integer> map = new TreeMap<>();
for(int[] q:questions){
	map.merge(q[1],q[0],Integer::sum);
	map.merge(q[2],-q[0],Integer::sum);
}
int pre = 0;
for(Map.Entry<Integer,Integer> e:map.entrySet()){
	pre+=e.getValue();
	// 通过前缀和还原原数组
}