C++教程

差分与前缀和是在优化数组存储时的主要的方法，下面我们来了解它们

前缀和

以下是两个数组

1,2,3,4, 5  //原数组
1,3,6,10,15  //前缀和处理

我可以明确的告诉你这就是前缀和
看出来了吗?前缀和数组a[n]就等于原数组b[n]项(含)前面的所有项目的和
放在递推里可以这样写

a[1]=b[1];
for(...){
    a[i]=a[i-1]+b[i];
}

那么前缀和有什么用呢?
他可以让我们更快的读取数组区间的和
以一维数组为例:
要求数组b[n~m]项的和ans,可以这样写

//a[]是b[]的前缀和数组
ans=a[m]-a[n-1];

差分

照样是两个数组

1,2,5,4,6
1,1,3,-1,2

有一点乱,但没关系,差分数组a[]和原数组b[]规律就是

a[n]=b[n]-b[n-1]

即是原数组的对应项与前一项的差
那么差分有什么用呢?
他可以让我们更快的改变数组区间内的值(同操作,如都+2)
如果要把b[n~m]的项目都+2怎么办呢?

a[n]+=2;
a[m+1]-=2;