在上篇文章当中讲述了前缀和的有关知识，这期给大家带来差分的知识。
首先什么是差分？
给一个原数组a[]，再给定一个差分数组g[]，那么原数组与差分数组的关系：
g[1] = a[1];? g[2] = a[2] - a[1];? g[3] = a[3] - a[2].....
那么我们通过对其关系可以推出：
g[1] + g[2] + g[3] = a[1] + (a[2] - a[1]) + (a[3] - a[2]) = a[3]
根据上面的等量关系，我们不难看出对差分数组前i个元素进行前缀和就会得到原数组a[i]的值。
那么直到这个性质后，我们再来研究差分数组有什么用处呢？
在讲述前缀和的作用，我们知道了前缀和可以快速求出某一段元素所对应的原数组的和，而差分可以快速的对某一段元素分别加或减值。
下面给出的是一维差分数组的计算方式：
#include <iostream>
using namespace std;
const int N = 1000;
int a[N],g[N];
void insert(int l,int r,int c)
{
g[l] += c;
g[r + 1] -= c;
}
int main()
{
int n;
for(int i = 0;i <= n;i++)
{
cin >> a[i];
insert(i,i,a[i]);//计算差分并赋值
}
for(int i = 0;i <= n;i++)
cout << g[i] << ' ';//打印差分数组
return 0;
}如果要是想在某段区间内每个元素对应的值+c：
#include <iostream>
using namespace std;
const int N = 1000;
int a[N],g[N];
int s[N];//记录差分数组前缀和后的数组
void insert(int l,int r,int c)
{
g[l] += c;
g[r + 1] -= c;
}
int main()
{
int n;
for(int i = 0;i <= n;i++)
{
cin >> a[i];
insert(i,i,a[i]);//计算差分数组
}
int m;
cin >> m;//输入更改次数
while(m--)
{
int l,r,c;//在l - r范围内的元素+c
cin >> l >> r >> c;
insert(l,r,c);
}
for(int i = 0;i <= n;i++)
s[i] = s[i - 1] + g[i];//用动态规划对差分数组前缀和将改完后的原数组的值存入s[]
for(int i = 0;i <= n;i++)
cout << s[i] << ' ';//输出改完后的原数组
return 0;
}对差分数组进行前缀和就可以得到原数组，那么接下来看一下二维差分数组：
首先其二维与前缀和的二维大概理解差不多，只不过其面积要理解成当前(i,j)点与右下角的点形成的矩形面积，对于二维差分矩阵：
g[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1]? ? (这个可以理解为前缀和反向计算原数组的含义)
要是对于二维原矩阵进行区间修改：
void insert(int x1,int x2,int y1,int y2,int c)
{
g[x1][y1] += c;
g[x2 + 1][y1] -= c;
g[x1][y2 + 1] -= c;
g[x2 + 1][y2 + 1] += c;
}因为g数组是a数组的差分数组，a数组是g数组的前缀和数组，所以g数组在a数组上代表的面积与前缀和代表的面积相反，是与右下角的点构成的矩形面积，所以通过面积作差得到原数组的值。
而其是以(x1,y1)为起点，在这里+c代表其整个矩阵内的所有元素分别+c，这样理解的话，为了让(x1,y1)与(x2,y2)构成的矩阵内的值+c就需要后面的三行进行调整(面积的割补)。
#include <iostream>
using namespace std;
const int N = 1000;
int a[N][N]; //原数组
int g[N][N]; //差分数组
void insert(int x1,int x2,int y1,int y2,int c)
{
g[x1][y1] += c;
g[x2 + 1][y1] -= c;
g[x1][y2 + 1] -= c;
g[x2 + 1][y2 + 1] += c;
}
int main()
{
int n,m,s;
cin >> n >> m >> s;
for(int i = 0;i <= n;i++)
{
for(int j = 0;j <= m;j++)
{
cin >> a[i][j];
insert(i,i,j,j,a[i][j]);//计算差分并赋值
}
}
更改s次，在(x1,y1)与(x2,y2)构成的矩阵内的值+c
while(s--)
{
int x1,y1,x2,y2,c;
cin >> x1 >> x2 >> y1 >> y2 >> c;
insert(x1,x1,y1,y2,c);
}
//利用动态规划进行前缀和
for(int i = 0;i <= n;i++)
{
for(int j = 0;j <= m;j++)
{
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];//差分矩阵前缀和(DP)
}
}
//打印
for(int i = 0;i <= n;i++)
{
for(int j = 0;j <= m;j++)
{
cout << g[i][j] << ' ';//打印更改后的原数组
}
cout << endl;
}
return 0;
}到这里不难发现求前缀和就是利用动态规划，而差分数组的赋值以及对原数组加减值是利用上面构造的insert函数，差分数组前缀和可得到原数组，前缀和数组进行差分同样也是可以得到原数组的。?
好了，本期内容就到这里了，后序会继续更新算法的相关知识。
感谢收看，记得三连支持一下。