前缀和与差分

前缀和

一维前缀和

二维前缀和

差分

参考——知乎

一维差分

原理

有数组 a [ ] = { a 1 , a 2 , … , a n } a[] = \{a_1, a_2,\dots,a_n\} a[]={a1?,a2?,…,an?}，现在构造一个数组 b [ ] = { b 1 , b 2 , … , b n } b[] = \{b_1, b_2, \dots, b_n\} b[]={b1?,b2?,…,bn?} ，使得
$$a_i=b_1+b_2+?+b_i$$
则称数组$b$为数组$a$的差分数组，数组$a$是数组$b$的前缀和数组。

用途

1. 在$O(1)$的时间复杂度内实现区间修改

例子：

假如现在要将数组$a$在区间$[L,R]$注意，为闭区间上的每个数均加上$x$，那么我们立马可知：

-$a[L]=b[1]+b[2]+?+b[L]$，故