前缀和与差分

对于一个数组a定义数组为a数组的前缀和数组。 
//为了避免数组越位，下标从1开始用
for(int i=1;i<=n;++i)
{
    s[i]=s[i-1]+a[i];
}

定义数组为a数组的差分数组。 
//为了避免数组越位，下标从1开始用
for(int i=n;i;--i)    //倒着for的可以不借助两个数组，这里用d和a是为了看着清楚，实际可以用一个数组储存。
{
    d[i]=a[i]-a[i-1];
}

前缀和与差分运算为互逆运算，任意一个数组a的前缀和数组的差分数组是它本身。

静态数组的区间求和问题 


int sum(int l,int r)
{
    return s[r]-s[l];
}

进行m次区间修改后的静态单点求值问题

假设需要操作的数组是数组a长度为8，一开始全为0。
下标 0 1 2 3 4 5 6
d
 0 0 0 0 0 0 0
a 0 0 0 0 0 0 0
假设说现在要对数组a的区间[1,4]加上一个5，我们观察对应差分数组d的变化
下标 0 1 2 3 4 5 6
d 0 5 0 0 0 -5 0
a 0 5 5 5 5 0 0
发现对于原数组a的区间加数操作对应差分数组d只改变了两个地方。
因为差分数组的前缀和数组为原数组，所以对差分数组的修改，在原数组上产生的影响是这个位置以后的一个后缀影响。
给d[l]加上x就相当于给a[l],a[l+1],a[l+2]....a[n]全部加上x。
给d[r+1]加上-x就相当于给a[r+1],r[r+2],....a[n]全部加上-x。
那么如果要给a[l],a[l+1]...a[r]全部加上x就很简单了。 
void add(int l,int r,int x)
{
    d[l]+=x;
    d[r+1]-=x;
}
注意我们操作的是数组d，是差分数组，不是原数组。也就是说如果你最后要输出原数组a的话还要在做一遍前缀和还原。

前缀和的前缀和

在上述求值问题中如果最后不是查询单点的值，而是查询区间和，那么就需要再求一遍前缀和。
第一次前缀和是为了将差分数组还原回原数组，而第二次前缀和是为了求前缀和数组。
对于一个数组a，它的差分数组d与前缀和数组s之间也是有关系的，数组s是数组d前缀和的前缀和，而数组d是数组s的二阶差分。
如果需要动态维护前缀和的前缀和，可参考

二维前缀和与差分

高维前缀和（SOSDP）

动态前缀和

线段树：