写在前面
本部分内容借鉴于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] + " ");
}
}
}
网友评论