前缀和与差分

前言

由于前缀和和差分一个加一个减，两个在写法上差距不大而且具有一定共同点，所以放在一块进行描述。

前缀和

前缀和介绍

前缀和顾名思义，就是一段数列前面某一段连续数列的和。

他经常用于预处理区间和的信息，通过预处理前缀和，我们可以快速的得到某段连续数列的和是多少。

当我们需要求取的区间和时，我们可以用来获取，经常会有人将减号后面写成，但是我们需要保留的和，需要减去的重复部分应该是之前的部分

前缀和模板

vector<int>a(n+1),sum(n+1);//a为原数组，sum为前缀和数组
for(int i=1;i<=n;++i){
	sum[i]=sum[i-1]+a[i];
}

差分

差分介绍

差分是相邻两个元素之间的差值，一般为后面的一个元素减前面的一个元素。

差分经常用于将区间加操作转化为单点加的操作，对于一段区间，若要对这段区间+1，可以转化为在差分数组中处+1,处-1，因为相比于多加了1，到区间内的差值都没有发生变化，而相比于也多加了1。

同时，差分数组的前缀和也是该位置原先的数字本身，这个点有时候会用到。

差分模板

vector<int>a(n+1),dif(n+1);//a为原数组，dif为差分数组
for(int i=1;i<=n;++i){
	dif[i]=a[i]-a[i-1];
}

总结

前缀和与差分往往都是对于区间查询、区间操作转化为单点查询、单点操作来降低时间复杂度。