差分

差分相当于前缀和的逆运算。

目的：数组中一段数+x时间复杂度降低

具体做法：假设一个数组的前缀和为原数组

一维差分：

预处理：

1
2
3
4
5
6
7
int a[N],b[N];
/*(1)*/for(int i=1;i<=n;i++)b[i]=a[i]-a[i-1];
/*(2)*/for(int i=1;i<=n;i++)
{
	b[i]+=a[i];
    b[i+1]-=a[i];
}

添加数：

1
2
3
4
5
6
7
int l,r,c;
while(m--)
{
	cin>>l>>r>>c;
    b[l]+=c;
    b[r+1]-=c;
}

二维差分：

差分函数：

1
2
3
4
5
6
7
void insert(int x1,int y1,int x2,int y2,int c)
{
    a[x1][y1]+=c;
    a[x2+1][y1]-=c;
    a[x1][y2+1]-=c;
    a[x2+1][y2+1]+=c;
}

预处理：

1
2
for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)insert(i,j,i,j,c);

添加数：

1
insert(x1,y1,x2,y2,c);