差分

发表于 更新于 分类于 ，
本文字数： 883

差分法的一二维实例与理解

一维差分

前缀和与差分为逆运算

数组a[N]为数据组

数组b[N],s[N]进行两种运算

前缀和运算:

1
2
3
4
for(int i = 1; i <= n; i++)
{ 
    s[i] += a[i] + a[i - 1]; 
}

差分运算：

1
2
3
4
for(int i = 1; i <= n; i++)
{
    b[i] = a[i] - a[i - 1];
}

（大概是这个意思吧···）

两个数组a[N],b[N]

满足a[i]=b[1]+b[2]+b[3]+···+b[i]，则称a数组为b数组前缀和数组，b为a差分数组

（构造方法：b[1]=a[1],b[2]=a[2]-a[1],b[3]=a[3]-a[2]···）

但是构造差分数组的过程并不重要(存在).

实现若干次将一个数组a[N]的[l,r]区间内的数加c

不使用前缀和 差分需要O(n)复杂度 使用则只需要O(1)时间复杂度

将a[N]数组的每一个数字假设为0,b[N]也同理

将原先a[N]中每一个数字如：a[i]，都看作是在b[i,i]插入了a[i]，因此差分数组的构造则可省略

1
2
3
4
5
void insert(int l, int r, int c)
{
    b[l] += c;
    b[r + 1] -= c;
}

只需要这样一个插入函数，即可实现算法.

综上所述

我习惯于构造一个全零记录数组.

记录[l,r]区间上放c的操作

最后前缀和运算后与数据数组相加

二维差分

同理于一维差分.

仍为创建一个全0数组假设其为差分数组 b[N][N]

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

将数据读入a[N][N]中，同样以一维数组的方式insert入b[N][N]中

再实现若干次将[x1,x2]到[x2,y2]作为两个对角的矩形区间内的数加c的操作

最后同样是将差分数组b进行前缀和运算

综上所述

我习惯创建一个记录数组

记录操作

最后再将记录数组求前缀和与原数据数组相加