前缀和与差分互为逆运算
一、一维前缀和
设有序列${a}_1,{a}_2,{a}_3......{a}_n$，则该序列的前缀和${S}_i={a}_1+{a}_2+{a}_3+......+{a}_i$
作用：快速求出${a}_l$到${a}_r$之间所有数的和：${S}_r-{S}_{l-1}$
二、二维前缀和
设有矩阵 $\begin{pmatrix} {a}_{11} &{a}_{12} & ...&{a}_{1n} \\ {a}_{21} &{a}_{22} & ...&{a}_{2n} \\ ...&... &... &... \\ {a}_{m1} &{a}_{m2} & ...&{a}_{mn} \\ \end{pmatrix}$ ，则该矩阵前缀和${S}_{i,j}={S}_{i-1,j}+{S}_{i,j-1}-{S}_{i-1,j-1}+{a}_{i,j}$
前缀和的数学意义：${a}_{11}$与${a}_{i,j}$所形成的矩形内部所有数的和，按照这个思路公式就很容易推啦
作用：求出${a}_{x1,y1}$与${a}_{x2,y2}$所形成的矩形内部所有数的和：${S}_{x2,y2}-{S}_{x1-1,y2}-{S}_{x2,y1-1}+{S}_{x1-1,y1-1}$
注意：前缀和的${S}_{0},{S}_{0,y},{S}_{x,0}$均为0，因为需要考虑边界情况
三、一维差分
设有序列${a}_1,{a}_2,{a}_3......{a}_n$，构造${b}_1,{b}_2,{b}_3......{b}_n$,使得${a}_{i}={b}_{1}+{b}_{2}+......+b{i}$
方法：使 $\left\{\begin{matrix} {b}_{1}={a}_{1} \\ {b}_{2}={a}_{2}-{a}_{1}\\ {b}_{3}={a}_{3}-{a}_{2}& & \\ ...... \\ {b}_{n}={b}_{n}-{b}_{n-1} \end{matrix}\right.$
tips:其实不需要考虑构造，因为差分数列就相当于在原数列全是0的基础上，在这个点加上对应数
{ //......
for (int i = 1; i <= n; i++) //初始化
{
scanf("%d", &a[i]); //读入
insert(i, i, a[i]); //构造差分 }
insert(l, r, c); //在l到r间加上常数c
}
}
void intsert(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}作用：使a的子数列区间$[l,r]$上的所有数$+C$，只需要将${b}_l+C$，${b}_{r+1}-C$
输出修改后的数列：
for (int i = 1; i <= n; i++)
{
b[i] += b[i-1]; //参考一维前缀和
printf("%d ", b[i]);
}四、二维差分
作用：使矩阵$\begin{pmatrix} {a}_{11} &{a}_{12} & ...&{a}_{1n} \\ {a}_{21} &{a}_{22} & ...&{a}_{2n} \\ ...&... &... &... \\ {a}_{m1} &{a}_{m2} & ...&{a}_{mn} \\ \end{pmatrix}$中的某一小块矩形同时加上某个常数，只需要将 $\left\{\begin{matrix} {b}_{x_{1},y_{1}}+C \\ {b}_{x_{2}+1,y_{1}}-C\\ {b}_{x_{1},y_{2}+1}-C& & \\ {b}_{x_{2}+1,y_{2}+1}+C \end{matrix}\right.$
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
scanf("%d", &a[i][j]); //读入
insert(i, j ,i ,j, a[i][j]); //构造差分
}
}
insert(x1, y1, x2, y2, c); //在(x1,y1)到(x2,y2)间的矩阵中每位加上常数c
}
void intsert(int x1, int y1, int x2, int y2, int c)
{
b[x1][y1] += c;
b[x2+1][y1] -= c;
b[x1][y2+1] -= c;
b[x2+1][y2+1] += c;
}输出修改后的数列：
for( int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; //参考二维前缀和
printf("%d", b[i][j]);
}
printf("\n");
}五、配套练习