[数据结构] 差分数组+前缀和

差分数组+前缀和

参考文章

• 差分数组+前缀和——小而美的算法
• 差分数组是个啥？能干啥？怎么用？
• 什么是差分数组？

差分数组的推导公式:
原数组为num,差分数组为diff,前缀和数组为sum,

diff[0] = num[0]
diff[i] = num[i] - num[i-1] 

前缀和的推导公式:

sum[0] = num[0]
sum[i] = num[i] + sum[i-1]

• 差分数组主要用来大范围的区间修改
• 前缀和主要用来大范围的区间查询

举个例子，假设原数组为num，差分数组为diff，前缀和数组为sum

• 建立差分数组

	0	1	2	3	4
num	1	3	5	2	8
diff(num)	1	3-1	5-3	2-5	8-2
diff	1	2	2	-3	6

• 建立前缀和数组

	0	1	2	3	5
num	1	4	8	6	14
sum(num)	1	+4	+8	+6	+14
sum	1	5	13	19	33

差分数组:

当需要对原数组元素区间频繁修改值时，
只需要对差分数组的做简单修改就可以，
例如要修改原数组范围[1,3]的元素全部+2，
只需要修改差分数组的diff[1] += 2和diff[3+1] -= 2
即：

• 当要修改区间[l,r]的元素全部+k时，只需要修改diff[l] += k和diff[r+1] -= k即可。

diff[l] += k
diff[r+1] -= k

前缀和数组:

当需要对原数组元素区间元素的和频繁查询时，
只需要建立前缀和数组就可大大提升查询速度，
例如要查询原数组范围[1,3]的元素和，
原数组 num = {1, 3, 5, 2, 8 }
前缀和数组 sum = {1, 4, 8, 6, 14 }
那么查询[1,3]的元素和，只需要查询sum[3] - sum[1-1]即可。
即:

• 当要查询区间[l,r]的元素和时，只需要查询sum[r] - sum[l-1]即可。

取回原数组

• 若要取回原数组，只需要对差分数组进行建立前缀和数组即是原数组。
• 同样的，只需要对前缀和数组进行建立差分数组也是原数组。

num = sum(diff)
num = diff(sum)

例子: 对差分数组进行建立前缀和数组即是原数组

	0	1	2	3	4
num	1	3	5	2	8
diff(num)	1	3-1	5-3	2-5	8-2
diff	1	2	2	-3	6
sum(diff)	1	+2	+2	-3	+6
num	1	3	5	2	8

例子: 对前缀和数组进行建立差分数组是原数组

	0	1	2	3	4
num	1	4	8	6	14
sum(num)	1	+4	+8	+6	+14
sum	1	5	13	19	33
diff(sum)	1	5 - 1	13- 5	19-13	33-19
num	1	4	8	6	14