前缀和

对于一个一维数组 a[m]

其前 i 项的和记作 s[i]

如果想要对 a[m] 中任意连续段的值进行求和，例如 a[l]~a[r]

则可使用前缀和数组进行 $O(n)$ 计算

int a[m],s[m];

s[0]=0;//定义s[0]的值，防止边界问题

for (int i=1;i<=m;i++){//从1开始
    cin>>a[i];
    s[i]=s[i-1]+a[i];
}

这样的话，s 数组中存储的值便是前 i 项 a 数组的和

a[l]~a[r] 的和等价于 s[r]-s[l-1]，多次调用时，降低时间复杂度

若存在一个二维数组 a[m][n]

求其前 i,j 项的二维前缀和有公式：

s[i][j]=s[i][j-1]+s[i-1][j-1]-s[i-1][j-1]+a[i][j];

不难推出s[l1] [r1] ~ s[l2] [r2] 的和

对求任意的(l1,r1)~(l2,r2)有：

sum=s[l2][r2]-s[l2][r1]-s[l1][r2]+s[l1][r1];

差分
差分可看作前缀和的逆运算

对于一个数组 a[n] 有：

a[0] a[1] a[2] a[3] ......a[n-2] a[n-1]

构造一个差分数组 b[n] 使得其中每一项都为数组 a 每项的差：

b[0]=a[0]

b[1]=a[1]-a[0]

......

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

不难看出 b 的前缀和为 a 中的每一项

a[n]=b[0]+b[1]+b[2]+......+b[n]

应用：一维差分

若想对 a 中 a[l]~a[r] 之间的每个数都加上 c

则可以做以下操作：

b[l]+=c
b[r+1]-=c

这样的话：

a[l]=b[0]+b[1]+......+b[l-1]+b[l]+c=a[l]+c
a[l+1]+c=b[0]+b[1]+......+b[l-1]+b[l]+c+b[l+1]
......
a[r]+c=b[0]+b[1]+......+b[l]+c......+b[r-1]+b[r]
a[r+1]=b[0]+b[1]+......+b[l]+c......+b[r-1]+b[r]+b[r+1]-c

差分的非朴素构造：

对于一个一维数组，可以通过上面的简单构造 b 数组来实现

若为非一维数组则可以如下方法进行构造：以二维数组为例

将数组 a[i][j] 假设为全 $0$ 数组，则 b[i][j] 也为全 $0$

这样对 a[i][j] 中的每一项之间进行插入操作

b[i][j]+=c  //将ij矩形内的数加上常数c
b[i-1][j]-=c
b[i][j-1]-=c//减去(i-1,j) (i,j-1)矩形内增加的常数c
b[i-1][j-1]+=c//(i-1,j-1)//矩形内的数做过+c—c—c的操作，需要再次—c恢复到初始状态

将 a[i][j] 的每个数之间插入 a[i][j] 的值即为 b[i][j] 的值

例如在 a[0][0] 与 a[1][0] 之间插入 a[1][0] 的值（在假设 a 数组为全 $0$ 的情况下）

应用：二维差分

在 a[i][j] ~ a[l][r] 区间内的所有数加上常数 c

首先对 a 数组进行插入值的初始化：

void insert (int i,int j,int l,int r,int c){//i>l;j>r
    b[i][j]+=c;
    b[l+1][r]-=c;
    b[l][r+1]-=c;
    b[l-1][r-1]+=c;
}//定义插入函数

//假定a数组为a[m][n]

for (int u=0;u<m;u++)
    for (int v=0;v<n;v++)
        intsert (u,v,u,v,a[u][v]);//对b数组初始化

再对 a 数组间的指定段进行插入操作则可得到答案