差分

本文主要是介绍差分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

差分

（一）一维差分

1.目的

​ 将一维数组中某一区间内的元素都加上（减去）一个数

2.实现

​ 将a[l~r]中的数都加上c，首先构建一个数组b，使得b数组的前缀和数组为a数组，那么我们称b数组为a数组的差分数组，a数组是b数组的前缀和

​ 那么如果我们将b[l]+c，因为a数组是b数组的前缀和，那么a[l]以及之后的a数组都会加上c，而我们只需要让a[l~r]中的数加上c，因此我们只需要让b[r+1]-c,那么a[r+1]以及之后的a数组都会减去c，因此我们将操作后的b数组求前缀和，就得到了我们所需要的a数组

3.代码

//将a[l~r]中的数都加上c
void add(int l,int r); //也可用于构造b数组
{
	b[l]+=c;
	b[r+1]-=c;
}

//之后对b求一维前缀和即可求出a数组

（二）二维差分

1.目的

​ 将二维数组中某一子矩阵中的元素都加上（减去）一个数

2.实现

//给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c
void add(int x1,int y1,int x2,int y2) //也可用于构造b数组
{
    b[x1][y1]+=c;
    b[x1][y2+1]-=c;
    b[x2+1][y1]-=c;
    b[x2+1][y2+1]+=c;
}

//最后对b数组求二维前缀和即可求出a数组

这篇关于差分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！