前缀和&差分

前缀和

#

数列的前n项的和,即 ps[i]=a[i]+ps[i-1]

作用：在 O(1) 的时间内查询任意连续区间的元素之和

差分

#

前缀和的逆运算，即 diff[i]=a[i]-a[i-1]

作用：在 O(1) 的时间内修改任意连续区间的值

$\displaystyle a_{i}=\sum^{i}_{k=1}diff_{k}$

$\displaystyle S_{i}=\sum^{i}_{j=1} \sum^{j}_{k=1}diff_{j}$