五分钟看懂前缀和与差分

基于二维数组的前缀和主要应用场景是可以在O(1)情况下求出任何子矩阵的和

例如：我们打算求红色子矩阵的和，我们可以使用紫色的子矩阵和-绿色的子矩阵和-蓝色的子矩阵和+黑色子矩阵和（因为黑色子矩阵在减绿色和蓝色时减了两次，所以要加上一个黑色）。我们使用s1的值表示黑色子矩阵的和，s2的值表示绿色子矩阵的和，s3表示蓝色子矩阵的和，s4表示紫色子矩阵的和，那么所求子矩阵和=s4(右下角)-s2(右上角)-s3(左下角)+s1(左上角)

经过上述例子我们可以看出，我们可以在O(1)情况下求出任何一个子矩阵的和。

看个具体例子，设s1的位置是(m,n)，s4的位置是(x,y)，则s2的位置是(x-m,y)，s3的位置是(x,y-n)

所求子矩阵和=s[x][y]-s[x][y-n]-s[x-m][y]+s[m,n];

求二维数组前缀和的方法（参考下图）：

int a[101][101],s[101][101]={0};
for(int i=1;i<=100;i++)
{
    for(int j=1;j<=100;j++)
    {
        cin>>a[i][j];
    }
}
for(int i=1;i<=100;i++)
{
    for(int j=1;j<=100;j++)
    {
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }
}

三、差分

对于差分来说，他的应用范围比较单一，主要用于可以让一个序列中某个区间内的所有值均加上或减去一个常数。

所以差分往往应用于线性的场合，即一维数组的环境。

差分是指，序列中每个元素与其前一个元素的差。

//设原数组为a
int a[100];
//设差分数组为b
int b[100];

根据定义可知：

b[i]=a[i]-a[i-1];
//注意：b[1]=a[1]

我们一般认为原序列就是差分序列的前缀和，所以把差分看做前缀和的逆运算，来看下面的例子：

//a[]为原数组,b[]为差分数组
b[1]+b[2]+……+b[i]
=a[1]+a[2]-a[1]+a[3]-a[2]+……+a[i]-a[i-1]
=a[i]
即a[i]=b[1]+b[2]+……+b[i]，所以原序列为差分序列的前缀和序列

一起来看个实际的例子：

a[5]=b[1]+b[2]+b[3]+b[4]+b[5]
    =a[1]+a[2]-a[1]+a[3]-a[2]+a[4]-a[3]+a[5]-a[4]
    =a[5]

我们来解释一下差分序列的作用：让一个序列中某个区间内的所有值均加上或减去一个常数

我们现在让区间[l,r]中的所有值均加上常数C，可以利用差分数组简单实现：

b[l]+=C;
b[r+1]-=C;

为何上面简短的两条语句就可以实现此功能呢，我们做一下解释：

//对于一个小于l值的原数据，我们可以利用刚才的逆运算，用差分序列求出原数据
a[l-1]=b[1]+b[2]+……+b[l-1];  //因为b[1]……b[l-1]中，所有值未改变，所以a[l-1]不变
//对于一个大于等于l和小于等于r的原数据，我们同样利用差分序列求原数据
a[l]=b[1]+b[2]+……+b[l-1]+b[l];   //因为b[l]+=C,所以a[l]增加了C
a[l+1]=b[1]+b[2]+……+b[l]+b[l+1]; //因为b[l]+=C,所以a[l+1]增加了C
.
.
.
a[r]=b[1]+b[2]+……+b[l]+……+b[r]; //因为b[l]+=C,所以a[r]增加了C

//对于一个大于r的原数据，我们同样利用差分序列求原数据
a[r+1]=b[1]+b[2]+……+b[l]+……+b[r]+b[r+1]; 
//因为b[l]+=C,所以a[r]增加了C,但又因为b[r+1]-=C,所以a[r+1]又减小了C，所以a[r+1]不变

根据以上推论，只有[l,r]中的原数据在原来的基础上均增加了C