写在前面
本部分内容借鉴于Young-children大佬对于差分数组的讲解，感谢大佬。
定义
差分数组类似于求解前缀和，给出原数组为d，差分数组为f，那么有f[i] = d[i] - d[i - 1]，据此，可以发现两条差分数组的性质：
-
d[i]等于f[i]的前缀和 -
d[i]的前缀和可以通过如下公式来求得：
用途
差分数组主要支持两种操作：1、区间修改；2、单点查询
根据性质一，可以得到若对某个区间[L, R] 增加一个数 x，只需要使 f[L] += x; f[R + 1] -= x; 即可实现对区间的批量修改，而查询时只需要求前缀和查询单个元素，或者通过上述性质二的公式查询前缀和/区间和即可
备注
实际使用差分数组时，并不一定需要使用源数组构造，可以直接根据区间修改来实现，详见1854. 人口最多的年份，同类型题号如下：370、731、732、995、1094、1109、1526、1589、1674、1854，另外，使用差分数组如果数据范围较大，需要使用TreeMap代替数组实现，本质大同小异
模板
由于差分数组实际上就是一个数组，并不需要什么模板，所以这里粘贴一道题目及题解。题目转自 acwing
题目
代码
import java.util.*;
class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int n = input.nextInt() + 1, m = input.nextInt();
int[] nums = new int[n];
for(int i = 1; i < n; i++){
nums[i] = input.nextInt();
}
int[] f = new int[n + 1];
for(int i = 1; i < n; i++){
f[i] = nums[i] - nums[i - 1];
}
for(int i = 0; i < m; i++){
int l = input.nextInt(), r = input.nextInt(), c = input.nextInt();
f[l] += c;
f[r + 1] -= c;
}
for(int i = 1; i < n; i++){
f[i] += f[i - 1];
}
for(int i = 1; i < n; i++){
System.out.print(f[i] + " ");
}
}
}
