信友队暑期总结
3.前缀和，差分，双指针
（1）一维前缀和
前缀和，通俗的说：对存有一些数字的某个数组而言,前缀就是指的其数组的前k项相加的值,因此对应的前缀和就是数组前k项的和。对一个数组，问[L,R]的区间和（从第L项到第R项的值相加的和），就可以利用前缀和进行求解。
sum[i]=sum[i-1]+a[i];
（2）二维前缀和
二维前缀和sum[i][j]记录a数组第1,1~i,j之间的所以数字和
公式：S[i][j] = a[i][j] + S[i-1][j] + S[i][j-1] - S[i-1][j-1]
求子矩阵和公式：sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]
（3）一维差分
数组a[1], a[2], a[3] …a[n]，数组b[1], b[2], b[3]…b[n]，其中，a[i] = b[1] + b[2] + b[3]…b[i]，称b是a的差分，相当于是前缀和的逆运算。
一维差分可以快速的将一个数组中的[l, r]中的元素都加上c，只需要对其差分数组进行上述操作。 进行d[l]+=c, d[r+1]-=c
（4）二维差分
作用：对一个矩阵的某个子矩阵的所有的元素加上c
数组a——二维前缀和数组， d——二维差分数组
求出二维差分数组d[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
进行：
d[x1][y1]+=c d[x2+1][y1]-=c d[x1][y2+1]-=c d[x2+1][y2+1]+=c
（5）双指针
作用：优化时间复杂度
