【总结】差分原理详解（通俗易懂）

秒速五厘米 2023-07-04 15:44 24阅读 0赞

**什么是差分？**

差分就是将数列中的每一项分别与前一项数做差。

首先一个数组 ：1 2 5 4 7 3

那么差分之后 ：1 1 3 -1 3 -4 -3

其实就是  a \[ i \] = a \[ i \] + a \[ i − 1 \] a\[i\] = a\[i\] + a\[i-1\] a\[i\]=a\[i\]\+a\[i−1\]

注意得到的差分序列第一个数和原来的第一个数一样（相当于第一个数减0）

差分序列最后比原序列多一个数（相当于0减最后一个数）

**差分一般使用场景：**

给出 n 个数，再给出 m 个询问，每个询问给出 l，r，x，要求你在 l 到 r 上每一个值都加上 x，而只给你 O(n) 的时间范围，怎么办？

如果暴力，时间复杂度就是 O(n^2)

如果线段树或者树状数组，时间复杂度就是 O(mlogn)

所以这里用差分，时间复杂度就是 O(n)

**具体操作：**

先另外开一个专门差分的数组

假如在 3~8 的区间上加上 5，那我们在差分数组中的 3 位置上加上一个 5 （原因暂时不懂没关系，用笔先跟着模拟），再在8+1的位置上减一个5,如此操作完 m 次

接着运用公式  a \[ i \] = a \[ i \] + a \[ i − 1 \] a\[i\] = a\[i\] + a\[i-1\] a\[i\]=a\[i\]\+a\[i−1\] 遍历一遍数组。那么你会发现在 3~8 的区间上，你已经使差分数组全部加上了 5 。

**来几道例题练练手**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]  
代码就自己去操作吧，多练才会！

**再来一道经典例题，专门卡时间，只能差分或者线段树或者树状数组才能过**

[经典例题：部落外的树][Link 1]

> 题解：[https://blog.csdn.net/weixin\_44668898/article/details/100751973][https_blog.csdn.net_weixin_44668898_article_details_100751973]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200212165145955.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDY2ODg5OA==,size_16,color_FFFFFF,t_70
[Link 1]: http://www.javatribe.org/problem/2019%E9%80%89%E6%8B%94%E8%B5%9BH%E9%A2%98
[https_blog.csdn.net_weixin_44668898_article_details_100751973]: https://blog.csdn.net/weixin_44668898/article/details/100751973