个人笔记，欢迎补充，指正。
一维前缀和
对于数组：
a[1],a[2],a[3]...a[n];其前缀和数组为
s[i] = a[1] + a[2] + ... + a[i];下标必须从1开始
求前缀和
1 for(int i=1;i<n;++i) 2 s[i] = s[i-1] + a[i];
作用
求原数组里一段数（l，r）的和sum
若不用前缀和，求一段数和需要从l遍历到r，时间复杂度O（n）。
用前缀和：
sum = s[r] - s[l-1];因为
s[r] = s[1] + s[2] + ... + s[l-1] + s[l] + ... + s[r];
s[l-1] = s[1] + s[2] + ... + s[l-1];
时间复杂度O（1）
注：该作用为前缀和最大的用处，也基本是唯一的用处。
s[0] = 0原因：
使得求s[i] 和 sum可以统一公式。
二维前缀和
对于矩阵： a[1][1] ~ a[x][y];
前缀和： s[1][1] ~ s[x][y];
求前缀和
上矩形的和加上左矩形的和减去左上矩形的和得出L形的和，加上a[i][j]。
1 for(int i=1;i<n;++i) 2 for(int j=1;j<n;++j) 3 s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1];
作用
求（x1,y1）到（x2,y2）矩形的和
sum = s[i][j] - s[i-1][j] - s[i][j-1] + s[i-1][j-1];
一维差分
对于数组
a[1],a[2],a[3]...a[n];
构造数组
b[i] = a[i] - a[i-1]
数组b则为a的差分
主要作用
区间修改
将a的（l,r）的数加上一个常数c，
常规做法是历遍l~r，给每个数加c，每次复杂度O（n）。
而如果给b[l]加上c，那么还原a的（l,n）都将加c，
再在b[r+1]减去c，那么还原后(l,r)都加c，其他部分不修改。
在需要多次修改时，只有最后复原是O（n），前面修改都是O（1）。
缺点是：静态，只能在修改完成后访问，否则时间复杂度O（n），无意义。