信息学编程知识 维数组差分

来源：深圳童程童美信息学培训学校时间：2023/12/7 10:08:42

　　一、差分：一维数组的差分可看作是一维数组前缀和的逆运算。

　　二、差分数组

　　首先给定一个原数组a: a[1]、a[2]、a[3]、......

　　然后构造一个数组b: b[1]、b[2]、b[3]....

　　使得a[i]=b[1]+b[2]+b[3]+b[4]+.....b[i]。

　　那么根据上一节讲的，a数组就是b数组的前缀和数组。

　　也就是说，a数组就是b数组的前缀和数组，反过来，我们把b数组叫做a数组的差分数组。话句话说，每一个a[i]数组都是b数组中从头开始的一段区间和。

　　三、功能及作用

　　给区间[L,R]中每个数加上 c: B[L] +=c， B[R+1] -=c

　　四、构造

　　考虑如何构造差分数组b：

　　较为直接的方法：

　　BASICa[0]=0

　　b[1]=a[1]-a[0];

　　b[2]=a[2]-a[1];

　　b[3]=a[3]-a[2];

　　......

　　b[n]=a[n]-a[n-1];

　　五、应用

　　【问题描述】给定区间[L,R]，让我们把a数组中的[L,R]区间中的每一个数都加上c， 即a[L]+c, a[L+1]+c, a[L+2]=c , .... a[R]+c

　　解法一：暴力解法

　　用for循环，从L到R区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，那么时间复杂度就会变成O(n*m)。

　　解法二：差分

　　始终要记住一点：a数组是b数组的前缀和数组。比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。

　　首先让差分b数组中的b[L]+c，通过前缀和运算，a数组变成a[L]+c,... a[L+1]+c,.... a[n]+c

　　然后我们打个补丁， b[R+1] -c ，通过前缀和运算， a数组变成 a[R+1]-c, ... a[R+2]-c, ... a[n] -c, ...

　　图解过程：

　　b[L]+c, 效果使得a数组中a[L]及以后的数都加上了c(红色部分)，但是我们只要求L到R区间加上c，因此还需要执行b[R+1]-c， 让a数组中a[R+1]以及往后的区间再减去c(绿色部分)，这样对于a[r]以后区间的数组相当于没有发生改变。

　　结论：给a数组中的[L,R]区间中的每一个数加上c。只需要对差分数组b做b[L]+=c，b[R+]-=c，时间复杂度为O(1)。

　　如果上面的描述不够清楚，我们可以借助下面方式来表示，我们假设a数组是原始数组，b数组是差分数组。我们的目的是让a数组的某个区间段加上一个数c。初始状态如下：

　　区间端点0123456

　　原始数组a[i]0

　　354897

　　差分数组b[i]

　　32-141-2

　　需求1：我们要将[1,4]范围内所有的数都加上3

　　区间端点0123456

　　原始数组a[i]0

　　3+3=65+3=84+3=78+3=1197

　　差分数组b[i]

　　3+3=62不变-1不变4不变1-3=-2-2

　　规律：当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反地变化。

　　那么用代码表示：

　　C++while(t--){//操作次数

　　cin>>x>>y>>change;//左右端点值

　　cin>>c;//c是每次加减的值

　　b[x]=b[x]+c;

　　b[y+1]=b[y+1]-c;

　　}

　　那么能不能反过来求a[i]呢，因为b数组是差分数组，满足公式b[i]=a[i]-a[i-1]

　　那么a[i]=a[i-1]+b[i]

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/2476/news/688454/违者必究！ 以上就是深圳童程童美信息学培训学校 小编为您整理 信息学编程知识 维数组差分的全部内容。