算法总结--差分！

· · 算法·理论

飞竹来也！
今天我们继续学习新的算法--差分！
大家还记得前缀和吗？一个可以O(1)查询区间和的简单算法

给你一个数组:

好的，请你给他做一个前缀和代码，我赌你一定会！
那么今天我们来点不一样的：差分（简称小差
差分的定义含简单，我们把它叫做d数组，
那么d_i就等于a_i-a _i _- _1,是不是很简单？
当你学会了这个模板后，你就觉得自己天下无敌了，NO,NO,NO这啥也不是，你还得学会还原？
还原是嘛？
呃......
我们只用把差分数组进行前缀和，那么sum_i就等于a_i，哇哇哇，太牛掰了！
这个在时间上特别有优势呢！（小差：腻害吧！

接着，如果我让你把[L,R]中的所有元素加上3,你肯定会，直接循环不就完了吗？
这年头，你还在用循环？也太low了吧！
这回，咱们就用差分数组来优化一波：
数学里说：同增同减差不变，所以我们只用改变差分数组中的2个元素就可以啦！
那这两个元素又是哪两位天选之素呢？

d_l$：因为他自己加了$3$，可他前面的$d$ $_l$ $_-$ $_1$可没加$3$,所以差分数组$d-l$要加$3 d_r$ $_+$ $_1$：因为$d_r$加了，可他自己没加，减数增加，差变少，所以他要$-3

改完后，你就基本了解差分了，接下来我们瞅一道题：P2367
语文成绩！

这道题就是经典的差分题，我们可以在每次加分的时候就把那两位天选的元素分别处理一下，最后用前面讲的方法，用前缀和还原原来的a数组就完事了快点解决吧！

下一道：
梦想家

看到这道题有没有一种一脸懵逼的感觉？
这道题前面和差分还有点相似，可当你看到这的时候，我相信你已经懵了：

这是神么鬼玩意？
别急，我们把它拆开：

也就是前一个元素小于后一个元素，那么下面的同理
前一个元素大于后一个元素

提起大于小于，我就想起了差分小差！
这不就可以转换为d_i了吗？
哇塞哇塞！尊嘟假嘟？
尊嘟！

那么接下来的我就不讲了
这就是差分典型的套路，把差分改为一个看似很复杂的公式
以后大家千万不要被他忽悠到了，他就是纸老虎！
再回到这道题，这道题和差分特别想，只不过他每次都让你输出魅力值，这就有点难办了？

别急，小差来了！
真相只有一个!无解
我们每次操作完，只会改变两个差分元素，也就是我们每次都只用把这两个元素对魅力值的影响处理一下就好了！
我们可以写一个函数，把刚刚转化为差分的公式放进去，算出每个差分元素对魅力值提供的价值。
接着，先用魅力值减去d_l原来提供的价值，改变d_l后，再算出他现在的价值，加回去，就阔以了！

注意：这道题出题人挖了坑！
只有LR不超过范围才会处理，不然就不动，懂了不？

来吧来吧，准备投喂绿题（小差:两眼放光！）
CF1442A

这道题题意很简单，可和其他题不同的，就在于他只能减前k个数或后k个数，尴尬了......
没关系，这道题如果你想通了就很简单，所以我们思考10分钟......

好的，时间到！
这道题我们只用考虑比前一个数字小的数字的与前一个数字的差，能否用d_1的高度来补上，请看这张图：

图中有一个坑，两个小山坡， 如果小山坡的土足够就可以填满，反之不能
这和这道题有什么联系呢？

小土坑是指那些大小超标的数，小山坡是指d_1, 我们需要用d_1的土，去填那些不满足大小的数，所以我们只用把所有<0的d_i加起来取个绝对值，再和d_1比大小，就可以得出答案了。
有同学说：我不可以从另一端d_n开始填吗？
从d_n开始，会让差分元素d_n _+ _1改变，而这样是无意义的，所以我们不从另一点开始。

今天的课就到这了！

和小差说再见，拜拜~~