前缀和与差分总结
一维：
前缀和的建立： sum[i] = sum[i-1] + val[i],
前缀和求解区间和： { val[l] ~ val[r] } = sum[r] - sum[l-1],
差分标记： [l,r]区间每个点增加v ， 则tag[l] += v， tag[r+1] -= v, 然后每个点 val[i] 的值的变化量delta即为 tag[]的1~i的一维前缀和
二维：
前缀和的建立： sum[i][j] = val[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] ,前缀和求解区间和：
差分标记： 以(a,b)为左上角, (c,d)为右下角的子矩阵的每个点增加v ： tag[a][b] += v， tag[a][d+1] -= v, tag[c+1][b]-=v, tag[c+1][d+1]+=v, 然后每个点 val[i][j] 的值的变化量delta即为 tag[][]的(1,1)~(i,j)的二维前缀和
三维：
前缀和求解区间和：（根据一维的情况与二维的情况， 应该可以总结得到sigma = sum[y1][y2]...[yn] - sum[x1-1][y2]..[yn] - sum[y1][x2-1]..[yn](将一个y换为x-1) +sum[x1-1][x2-1]..[yn] ...(将二个y换为x-1) - (将三个y换为x-1) +((将四个y换为x-1))， 类似容斥原理，故和式***有C(n,0)+C(n,1)+..+C(n,n) =2^n 项） （xi<=yi） 前缀和的建立： 类比前缀和求解区间和的公式的规律，根据二维的公式拓展即可
差分标记：类比二维形式建立。
对于N维情况，等号右侧应该是有
项。
查看2道真题和解析