差分

· · 个人记录

定义：

a数组是diff数组的前缀和，换句话说就是diff数组是a数组的差分数组。所以前缀和与差分是 共轭逆推 关系，所以可以推导出：diff[i]=a[i]-a[i-1]

应用

如果我们想让某个区间加或减一个数,就可以用差分，o(1)的时间复杂度，a[l]+=t,a[r+1]-=t;就行了

经典例题：

P2367 语文成绩

n<=5×10^6,暴力行不通，就可以用差分

把每个区间都用a[l]+=t,a[r+1]-=t，处理，再跑前缀和加上原本的分数取最小值就行了

P7404 [JOI 2021 Final] 有趣的家庭菜园4

允许选一个区间全部加1，对于a数组来说，选2个点，使得a[l]++,a[r]--

先把a数组全部求出来，然后两个指针，前面的数找到小于等于 0的数时就停下，后面的数栈到大于等于0的数时就停下，然后开始对调。其中一个满足了就继续移动。

二次差分

P4231 三步必杀

公差(c)：(e-s) / (r-l) ，项数(x)：r-l+1，把公式先列出来

然后在 s_l 到 s_r 中间插入一个上面的等差数列

那么 a_l += c , a_{l+1} += c , .... a_r += c , a_{r+1} -= c*x

换到diff数组里就是 diff_l += c ，diff_{r+1} -= c ，同理，diff_{r+1} -= c*x，diff_{r+2} = c*x

然后每一次输入的时候放进去就可以了。

但是没考虑到首项和公差不相等

所以应该是这样：a[l]+=s , a[r+1]-=s, a[l+1]+=c, ...... a[r]+=c, a[r+1] -= c*(x-1)

换成diff数组就是diff[l] += s, diff[l+1]-=s, diff[r+1]-=s, diff[r+2]+=s, diff[l+1]+=c,

diff[r+1]-=c, diff[r+1]-=c(x-1), diff[r+2]+=c(x-1)