前缀和
前缀和可以简单理解为「数列的前 n 项的和」
对于一维前缀和 简单的处理方式为b[i]=b[i-1]+a[i]
对于二维前缀和
有
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]
访问任意矩阵前缀和为
sum[l2][r2]-sum[l1-1][r2]-sum[l2][r1-1]+sum[l1-1][r1-1]
差分
差分是一种和前缀和相对的策略，可以当做是求和的逆运算。
它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。
即区间修改，单点查询
差分使
b[1]=a[1] for(int i=2;i<=n;i++) b[i]=a[i]-a[i-1]
这样 a[i]的值即为b[i]的前缀和
即 a[n]=sum(b[1~n])
a[i]的前缀和也可以用差分数组求出
for k=i k<=n k++: sum+=(n-i+1)*b[k]
使用差分数组时 若使[l,r]区间都加上k 那么b[l]+=k , b[r+1]-=k即可