差分数组

定义

对于第$i$位，记录第$i$位减第$i-1$位的差值。

例子：

下标	0	1	2	3	4	5	6
原数组	0	6	9	5	4	7	3
差分数组	0	+6	+3	-4	-1	+3	-4

用途

快速进行区间修改操作。

注意! 只适用于可被抵消贡献的运算中，如$+/-/\and$​(加、减、异或)等。

若将原数组$[l,r]$区间内加$val$，则相当于将差分数组第$l$位加$val$，第$r+1$位减去$val$(将贡献抵消)。

注意! 是第$r+1$位，而不是第$r$​位!!!

经常和维和区间和的数据结构一起使用。(树状数组等)