前缀和

前缀和可以理解为数列前n项的和。一般讨论一维前缀和与二维前缀和。

一维前缀和

给定一个一维数组A[]，它的前缀和S[n]就是数组A[]的前n项和
公式为： $S[n]=\sum_{i=0}^n A[i]$S[n]=i=0∑n​A[i]
递推公式为$S[1]=A[1]，S[i]=S[i-1]+A[i]$S[1]=A[1]，S[i]=S[i−1]+A[i]

自然可以得出其具有的性质：$A[n]=S[n]-S[n-1]$A[n]=S[n]−S[n−1]

可以进一步扩展，设某区间[L,R]，则$S[L]=\sum_{i=0}^LA[i]，S[R]=\sum_{i=0}^RA[i]，$S[L]=i=0∑L​A[i]，S[R]=i=0∑R​A[i]，

因此（求一个区间的和）：$\sum_{i=L}^RA[i]=S[R]-S[L]$i=L∑R​A[i]=S[R]−S[L]

前缀和也可以实现快速的区间上的加减，
若需要对数组A进行m次修改，每次修改是给某区间[L,R]每个元素同时+x，并求出修改后的数组A的前缀和：
方法是申请一个新数组p[]={0}，对于每次修改都使用下面的公式$p[L]+=x，p[R+1]-=x$p[L]+=x，p[R+1]−=x
修改完毕后再求p数组的前缀和P[]，然后A[i]+=P[i]，然后再对数组A求前缀和即可。（因为数组p求前缀和时，相当于[L,R]都+x，再加回到A数组上就获得新数组A了）

二维前缀和

给定一个一维数组A[][]，它的前缀和S[n][m]公式为： $S[n][m]=\sum_{i=0}^n\sum_{j=0}^m A[i][j]$S[n][m]=i=0∑n​j=0∑m​A[i][j]
递推公式为$S[1][1]=A[1][1]，S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j]$S[1][1]=A[1][1]，S[i][j]=S[i−1][j]+S[i][j−1]−S[i−1][j−1]+A[i][j]

这个递推式与一维有差距，但结合图片就很好理解了

很明显S[][]就是所包括的矩形范围内所有A数组元素的和，而两个绿矩阵相加再减去红矩阵，再加上A[i][j]就等于黑色的大矩阵，这也是上面递推式的由来。
与一维前缀和同理，设某区间为[l，r，L，R]（即左上角坐标与右下角坐标）
$S[l][r]=\sum_{i=0}^l\sum_{i=0}^rA[i][j]， S[L][R]=\sum_{i=0}^L\sum_{j=0}^RA[i][j]$S[l][r]=i=0∑l​i=0∑r​A[i][j]，S[L][R]=i=0∑L​j=0∑R​A[i][j]

所以某区间[L₁，R₁，L₂，R₂]中元素的和sum[L₁，R₁，L₂，R₂]时，有如下公式：
$sum[L_1，R_1，L_2，R_2]=S[L_2][R_2]-S[L_1][R_2]-S[L_2][R_1]+S[L_1][R_1]$sum[L1​，R1​，L2​，R2​]=S[L2​][R2​]−S[L1​][R2​]−S[L2​][R1​]+S[L1​][R1​]