type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于：My Blog 欢迎大佬们前来逛逛
差分介绍
差分是一种常见的算法，用于快速修改数组中某一段区间的值。
差分的思想就是预处理出数组的差分数组，然后修改区间时，只需要修改两个位置的值，即可快速完成区间修改。最后再通过差分数组求出原数组。 差分数组 d_i 表示原数组中相邻两个元素之间的差值，即，其中 a_i 表示原数组中第 i 个元素的值。则对于区间 [l,r] 的加上 k 的操作，可以表示为： 这样就完成了区间加 k 的操作。最后只需要用差分数组求出原数组即可。
差分应用
区间加
以区间加为例，设 a_i 表示原数组中第 i 个元素的值，d_i 表示差分数组中第 i 个元素的值，则对于区间 [l,r] 的加上 k 的操作，可以表示为： 最后只需要用差分数组求出原数组即可：以下是区间加的代码实现：
区间求和
另一种常见的操作是区间求和。设 a_i 表示原数组中第 i 个元素的值，d_i 表示差分数组中第 i 个元素的值，则对于区间 [l,r] 的求和操作，可以表示为：这样就能用差分数组快速求出区间和了。 以下是区间求和的代码实现：
总结
差分是一种常见的算法，用于快速修改数组中某一段区间的值。差分的思想就是预处理出数组的差分数组，然后修改区间时，只需要修改两个位置的值，即可快速完成区间修改。最后再通过差分数组求出原数组。差分算法在区间加、区间求和等问题中都有广泛的应用。
3729. 改变数组元素
题目要求：初始给你一个全为0的序列，给你一组数据，其中每一个数组a[i]=n表示对自 i 开始的的前面n个元素全都都变为1，已经是1的不予理会，求得操作完成后的数列的值。
示例：
操作后：
对于【2】位置，它的值为3，意味着自位置 2开始，前3个元素全部都变为1，则：
差分数组：[0]=1，[3]=-1。
我们根据差分数组转换为原数组：1到3的元素就是 1 1 0，这样我们就成功的利用差分数组改变了原数组的值。
因此对于每一个位置的值，我们对差分进行操作，b[l]+=1，b[r]-=1，最后利用差分数组转换为原数组。
注意几个地方：
- 如果根据所给的值得到对差分数组操作的 l 与r？ 假设我们的值为x，则左端点为 i-x+1，右端点为 i
- x必须取 i 和 x 的最小者，原因是即使 x大于i，则 i-x会得到一个负值，我们使得x=i，那么这样的话就是默认左端点为1开始
- 只需对差分数组进行操作
- 根据差分数组反推出原数组
- 我们只需要得到每一个位置的值是0还是1即可，对于原数组我们根据其值进行两次 ！！的操作，这个操作可以使得 0值仍然是0值，任意非零值都是1
- 注意清空差分数组的元素值。
100. 增减序列
题目要求：每次对某个区间进行操作可以选择整体加1，或者整体减1，使得整个数列的值全部相等，求得最少操作次数与最少操作次数对应的整个数列值的不同方案。
操作后得：
最少操作次数为2，即我们把 1到2的1整体加1，即可得到全部为2；把3到4的2整体减1，可以得到全部为1，这两种操作的最少操作次数都是1次，对应的方案数有两种
如果我们要想把全部的数列的值都变为唯一的值，则它对应的差分数组的值一定是：
即b[1]=num，往后每一个 b的值都为0，这样我们就得到了一个全部值都相同的原数组。
因此我们该如何构造一个这样的差分数组呢？
- 只有首元素不为零
- 差分数组中 2到n的全部元素都为0
可以发现：
- 最少操作次数：把差分数组变为上面的情况的最少操作次数
- 对应的方案数：因此就是求 b[1] 有多少种方案，就是数列中不同的值的种类
则在区间【2，n】中：
由于差分数组中值有正有负，因此我们根据贪心的思路：
每次选择两个符号不同的数值，一个加1，一个减1，这样就能用最少的次数将正负两个符号不同的数字相消
我们规定pos为差分数组中所有正数的和，neg为所有负数的绝对值的和。
则min(pos,neg)就是正数与负数进行相消的方案数，然后使得数列中所有的值都是相同符号：
假设差分数组为：2 5 -2 3 -1pos=8，neg=3，则我们经过 min(8,3)=3，即经过了三次操作使得所有的负数都消失：2 3 0 2 0 (两个负数一个加2，一个加1，对应其他位置一个减2，一个减1)
然后我们得到了全部都是符号相同的序列，下一步我们就是把【2，n】中所有的符号相同的数相消，使得数列中只留下【1】位置的值，则对于【2，n】中的数字可以有两种方案进行相消：
- 与【1】位置的值进行相消，此时会改变【1】的值
- 与【n+1】位置的值进行相消，此时不会改变【1】的值，【n+1】位置的值无意义。
因此我们再经过 |pos-neg|次操作使得所有的【2，n】位置的元素全部变为0，对于最少操作次数，选择两种方案都是一样的，因此最少操作次数为：
如果要统计对应的最少操作次数的方案数：则一定是 |pos-neg|+1。
上面相同符号进行相消配对的时候，选择 |pos-neg| 个与[1]匹配，则[1]改变，可以造成|pos-neg|个[1]的不同情况；另外选择[n+1]，则[1]不变，可以造成1种[1]的情况。
因此最终的组合数就是 |pos-neg|+1
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/4f1939a4-7644-4b05-848a-121617049565
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。