差分和前缀和算法

首先声明，差分和前缀和都的下标都建议从1开始，本文中将采取这种方式。

前缀和

所谓前缀和算法，其实就是预处理从开头到某个下标为止的和，进而可以在O(1)的时间复杂度内快速求出[l,r]的和。

一维前缀和

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

二维前缀和

S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

差分

所谓的差分其实是前缀和的逆操作

差分数组的前缀和就是原数组

差分的作用是将在[l,r]区间内所有数加c的操作转化为线性的对差分数组s[l]+c;s[r+1]-=c;的操作

与前缀和不同的是，不用专门去求差分数组，只需要将差分数组初始化为0，然后去l=r=i然后加a[i]的操作的就可以了。

一维差分

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

二维差分

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c