差分

id: differential

[[TOC]]

差分

设原数组的第ii个元素为aia_i,那么差分数组的第ii个元素为di=ai−ai−1d_i = a_i- a_{i-1}

有一组数据如下

下标123456原数组 a[i]351784差分数组 d[i]32−461−4差分数组d前缀和 s[i]351784\begin{array}{r|c|c|c|c|c|c} \text{下标} & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \text{原数组 } a[i]& 3 & 5 & 1 & 7 & 8 & 4 \\ \text{差分数组 } d[i]& 3 & 2 & -4 & 6 & 1 & -4 \\ \text{差分数组$d$前缀和 } s[i]& 3 & 5 & 1 & 7 & 8 & 4 \\ \end{array}

发现:对差分数组进行前缀和操作,就可以得到原数组了

Si=∑j=1idi=d1+d2+⋯+di=(a1−a0)+(a2−a1)+⋯+(ai−ai−1)=(a1−a0)+(a2−a1)+⋯+(ai−ai−1)=ai−a0      因为a0=0=ai\begin{aligned} S_i = \sum_{j=1}^i d_i &= d_1 +d_2 + \cdots + d_i \\ &= (a_1 - a_0) + (a_2 - a_1) + \cdots + (a_i - a_{i-1}) \\ &= (\bcancel{ a_1 } - a_0) + (\bcancel{a_2} - \bcancel{a_1}) + \cdots + (a_i - \bcancel{a_{i-1}}) \\ & = a_i - a_0 \;\;\; \text{因为$a_0 = 0$} \\ & = a_i \end{aligned}

现在对原数组aa的区间[2,4][2,4]上的每个数都增加22,得到如下

下标123456原数组 a[i]373984差分数组 d[i]34−46−1−4差分数组d前缀和 s[i]373984\begin{array}{r|c|c|c|c|c|c} \text{下标} & 1 & \color{Blue}{2} & \color{Blue}{3} & \color{Blue}{4} & 5 & 6 \\ \hline \text{原数组 } a[i]& 3 & \color{Blue}{7} & \color{Blue}{3} & \color{Blue}{9} & 8 & 4 \\ \text{差分数组 } d[i]& 3 & \color{Blue}{4} & -4 & 6 & \color{Blue}{-1} & -4 \\ \text{差分数组$d$前缀和 } s[i]& 3 & \color{Blue}{7} & \color{Blue}{3} & \color{Blue}{9} & 8 & 4 \\ \end{array}

发现,对原数组进行区间[2,4][2,4]修改: 差分数组只会修改两个值，第一个值为b2=b2+2b_2 = b_2+2，第二个值为b5=b5−2b_5 =b_5-2,且对修改后的差分数组进行前缀后依然得到了原数组.

于是,得出结论,如果对原 数组进行区间[l,r][l,r]上的每个数都增加vv,那么对应的差分数组只需要修改两位置bl=bl+vb_l = b_l+v, br+1=br+1−vb_{r+1} = b_{r+1}-v.原来需要r−l+1r-l+1次的区间操作,现在只需要进行22次区间操作.也就是++把区间增减转了两次的单点增减++.大大节省了时间

对于,那些题目

  • 多次区间修改(增减)
  • 一次查询(查询原数组的值)

适合使用差分思想(把原数组转化成差分数组来操作)

思考与总结

差分是前缀和的逆运算

已知,原数组aa就是数组ss,两者一模一样.所以在这里我们其实是先假定数组aa是数组dd形成的前缀和数组,进行就想到++能否通过前缀和数组aa推导出数组dd呢?++

我们现在认为原数组aa上每个值aia_i都是某个数组dd的前缀和.那么可以得到

ai=ai−1+di(1) a_i = a_{i-1} + d_i \tag 1

移项,进而得到

di=ai−ai−1(2) d_i = a_i - a_{i-1} \tag 2

通过(2)(2)式,把数组aa转化成dd数组.也就是前缀和数组转化成差分数组

可以通过aa得到dd,也可以通过dd得到aa,他们互为逆运算

a⇌d a \rightleftharpoons d

可以认为,aa与dd是同一事物的不同表现形式.

综上,可以得到如下的性质:

设dd是原数组,aa是dd的前缀和,

  • 在dd的两个位置i,ji,j上,同时+v,−v+v,-v,也就是di=di+v,dj=dj−vd_i = d_i+v,d_j = d_j-v,那么体现到aa上,那就是区间[i,j−1][i,j-1]上的每个数都增加vv
  • 在aa上的区间[i,j−1][i,j-1]上的每个数都增加vv,那么体现到dd上,那就是位置i,ji,j,+v,−v+v,-v,也就是di=di+v,dj=dj−vd_i = d_i+v,d_j = d_j-v

函数思想

设aa是一个数字组成的序列,定义函数如下:

  • f(a)=bf(a) = b,把序列aa转化成bb,其中bi=∑1iaib_i = \sum_1^i a_i,也就是前缀和
  • f−1(a)=bf^{-1}(a) = b,表示把序列aa转化成bb,其中bi=ai−ai−1b_i = a_i - a_{i-1},也就是差分

显然ff与f−1f^{-1}互为逆运算,也就是

f−1(f(a))=af(f−1(a))=a \begin{gather} f^{-1}(f(a)) = a \\ f(f^{-1}(a)) = a \end{gather}

同样可以想到ff与f−1f^{-1}是++双射函数++,也就是f(a)=bf(a) = b 也就是说ranfranf与domfdomf++一一映射++

定义函数range(a,l,r)range(a,l,r)，表示对序列aa区间[l,r][l,r]上的每个数都增加11

range(a1,l,r)=a2 range(a_1,l,r) = a_2

表示a1a_1经过区间[l,r][l,r]上的 每个数都增加11后得到a2a_2,显然a1≠a2a_1 \neq a_2,则f−1(a1)=d1≠f−1(a2)=d2f^{-1}(a_1) = d_1 \neq f^{-1}(a_2) = d_2^[因为一一映射的性质]

根据差分的性质知d1,d2d_1,d_2只有两个点不同,且这两个点是l,r+1l,r+1

定义函数

定义函数add(a,l,r)add(a,l,r)，表示对序列aa上的两点l,r+1l,r+1分别+1,−1+1,-1

add(a1,l,r)=a2 add(a_1,l,r) = a_2

则range(a1,l,r)range(a_1,l,r)与add(d1,l,r)add(d_1,l,r)是++一一映射++的.也就是每一个在序列a+1a+1上的rangerange操作,都等价于在序列d1=f−1(a1)d_1 = f^{-1}(a_1)上的add操作^[这里其时使用了反证法]

二维差分

11−9−3511−9−3511−9−35 \def\arraystretch{2} \begin{array}{|c : c : c:c|} \hline 11 &-9& -3& 5\\ \hline 11 &-9& -3& 5\\ \hline 11 &-9& -3& 5\\ \hline \end{array}

根据上面的思考,可以认为此时的二维矩阵上的值,都是每个二维矩阵dd的前缀和.也就是

⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡⊡ \begin{array}{cccccc} \color{Blue}{\boxdot} & \color{Blue}{\boxdot} &\color{Blue}{\boxdot} & \color{Green}\boxdot & \boxdot \\ \color{Blue}{\boxdot} & \color{Blue}{\boxdot} &\color{Blue}{\boxdot} & \color{Green}\boxdot & \boxdot \\ \color{Blue}{\boxdot} & \color{Blue}{\boxdot} &\color{Blue}{\boxdot} & \color{Green}\boxdot & \boxdot \\ \color{Green}{\boxdot} & \color{Green}{\boxdot} &\color{Green}{\boxdot} & \color{Red}{\boxdot} & \boxdot \\ \boxdot & \boxdot & \boxdot & \boxdot & \boxdot & \end{array}
Si,j=Si−1,j+Si,j−1−Si−1,j−1+di,j S_{i,j} = S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1} + d_{i,j}

移项,得到原二维矩阵上的每个值为:

di,j=Si,j−Si−1,j−Si,j−1+Si−1,j−1 d_{i,j} = S_{i,j}-S_{i-1,j}-S_{i,j-1} + S_{i-1,j-1}

对SS矩阵上的子矩阵(xi,yi),(xj,yj)(x_i,y_i),(x_j,y_j)进行+v+v操作,反应到dd上就是

  • (xi−1,yi−1),(xj+1,yj+1)(x_{i-1},y_{i-1}),(x_{j+1},y_{j+1})上的每个数都+v+v
  • (xi,yj+1),(xj+1,yi)(x_{i},y_{j+1}),(x_{j+1},y_{i})上的每个数都−v-v

小技巧: 点di,jd_{i,j}的值是Si,j−Si−1,j−Si,j−1+Si−1,j−1S_{i,j} - S_{i-1,j} - S_{i,j-1} + S_{i-1,j-1}, 也就是说,与以i,ji,j作为左下角的四个格子的值有关.也就是说i,ji,j的覆盖范围,有奇数个+v+v时才会产生影响.

martix

题目: [ luogu P3397: 地毯]

练习题目

暂无题目