AcWing—差分算法

文章目录

AcWing---差分算法
- 一、什么是差分？
- 二、差分的作用
- 三、一维差分模板
- 四、二维差分
- 五、二维差分构造方法图示：
- 六、二维差分矩阵模板
总结

差分算法是前缀和算法的逆运算。两者可以对比着学习：

一、什么是差分？

在这里插入图片描述
差分的概念是相对与前缀和说明的。

二、差分的作用

在这里插入图片描述
我们画图解释一下这里很容易出错：

我们从l开始都加了C，但是只是区间[l,r]上加C，所以我们从r+1开始就减去C，最后的结果是只有所选区间的每一个数增加了C。
之前我们给所选区间每个数加C它的时间复杂度是O(n),使用差分算法之后时间复杂度可以提升到O(1),只需要修改下面两步即可：
在这里插入图片描述
很对人都在考虑如何构造差分数组，其实不需要担心。
我们假设：

三、一维差分模板

给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

四、二维差分

一维差分是在一段上插入C，而二维差分就是在一个子矩阵加上C，原理类似：
在这里插入图片描述

五、二维差分构造方法图示：

在这里插入图片描述

六、二维差分矩阵模板

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

总结

今天分享了差分算法，这个算法可以和之前的前缀和算法比较着学习，这两个算法的关系很紧密，理解了其中一个另外一个也很容易理解，作用就是给所选区间中的每个数加上C，提高时间效率，使时间复杂度达到O(n),希望对大家有帮助，我们明天见~

上一篇：Java——后端开发经验总结（持续更新中）

下一篇：大麦 Android 选座场景性能优化全解析

蓝桥杯必备算法分享——差分算法