差分
理解关键:更新差分数组中一个元素后对原数组哪些元素产生影响.
思想:把对原数组的更新操作施加在差分数组上.最后计算原数组.
一维差分
1.含义
数组:a1,a2,...,an
差分数组:b[], ai = b1 + b2 + ... + bi
a[]称为b[]的前缀,b[]称为a[]的差分.即前缀与差分互为逆运算.
2.如何构造?
bi = a[i] - a[i-1](不重要)
3.应用
一组对数组一段连续区间[L,R]的操作,最后问更新后的数组.(先更新后询问,如果交替进行那么要用到
线段树.)
4.实现及理解
对原数组连续区间[L,R]加上c: b[L] += c , b[R+1] -= c
根据差分定义:ai = b1 + ... + bi, 也就是当b[L]+c后,所有i>=L的a[i]都增加了c,但
我们不想更新到R之后的元素,所以在R之后的元素减去c.
b[L] += c影响之后的元素
b[R+1] -= c消去R之后+=c产生的影响.最后更新的就是[L,R]
对于差分构造的操作可以并入插入操作:a[i]初值为c可以看成区间[i,i]加c.
更新之后的原数组用前缀的方式求得.(定义)
时间复杂度
插入O(1)
求原数组:O(n)(构造前缀和的时间复杂度)
C++ 代码
#include<cstdio>
const int Max_N = 1e5 + 10;
int n, m;
int b[Max_N];//差分数组
//更新区间[l,r] +c
void insert(int l, int r, int c)
{
b[l] += c; b[r+1] -= c;
}
int main()
{
scanf("%d%d",&n,&m);
for( int i = 1; i<=n; i++ )//构造->插入
{
int c;
scanf("%d",&c);
insert(i,i,c); //在[i,i]插入c
}
while( m-- )
{
int l, r ,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);
}
//求原数组:前缀和构造
for( int i = 1; i<=n; i++ )
{
b[i] += b[i-1];
printf("%d ",b[i]);
}
puts("");
return 0;
}
二维前缀和
1.含义:
与一维类似.
二维数组a[i,j]
差分数组b[i,j] : a[i][j] = sum( b[i'][j'] ) 1<=i'<=i,1<=j'<=j.即a是b的二维前缀和.
2.应用
一维差分数组应用于一组对连续区间的更新.二维差分数组应用于一个子矩阵的更新.
3.实现及理解
子矩阵左上角坐标(x1,y1),右下角坐标(x2,y2).子矩阵所有元素+c:
b[x1][y1] += c; b[x1][y2+1] -= c; b[x2+1][y1] -= c; b[x2+1][y2+1] -= c;
b[x1][y1] += c 对原数组元素的影响(右下角矩形)
为消去多余影响,我们需要在(x1,y2+1),(x2+1,y1)处-c消除影响.而(x2+1,y2+1)的右下角被消去两次,
所以要加回去.
时间复杂度
插入:O(1)
求更新后的原数组:O(nm) (二维前缀和构造的时间复杂度)
C++ 代码
#include<cstdio>
const int Max_N = 1010;
int n, m, q;
int d[Max_N][Max_N];//差分数组
//插入操作
void insert(int x1, int y1, int x2, int y2, int c)
{
d[x1][y1] += c;
d[x1][y2+1] -= c;
d[x2+1][y1] -= c;
d[x2+1][y2+1] += c;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for( int i = 1; i<=n; i++ )//构造->插入
{
for( int j = 1; j<=m; j++ )
{
int c;
scanf("%d",&c);
insert(i,j,i,j,c);
}
}
while( q-- )
{
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
insert(x1,y1,x2,y2,c);
}
for( int i = 1; i<=n; i++ )
{
for( int j = 1; j<=m; j++ )
{
d[i][j] += d[i][j-1] + d[i-1][j] - d[i-1][j-1];//前缀和的构造
printf("%d ",d[i][j]);
}
puts("");
}
return 0;
}