学习博客：差分数组详解_zsyz_ZZY的博客-CSDN博客_差分数组
给定一个源数组a，后续会对a数组其中区间进行+-操作，最后会需要计算和和期间某一个下标对应字符变化的时候可用。
如：
有源数组a。
还有动作数组b。
b中某一组会对a的 [ L, R ] 进行 +x 操作，也就是说从a[ L] 到a[ R]位置的所有源数组内容都需要+x。且这样的 b操作有多个。
这时候我们暴力循环肯定是性能很差会超时。因此需要使用差分数组。
下面我们设定四个数组：before[ i ], diff[ i ], after[ i ]，sum[ i ]；
before：表示原数组，
diff：是差分数组，
after：是修改后的数组，
sum：是前缀和数组。
当 i = 0 的时候：before[ 0 ] = diff [ 0 ] = after [ 0 ] = sum [ 0 ]
diff [ i ] = before[ i ] - before[ i-1]；
after [ i ] = after [ i - 1 ] + diff [ i ]；即 diff 数组的前缀和。
sum [ i ] = sum[ i - 1 ] + after [ i ]；即 after 数组的前缀和。
由此我们可以得到下列公式：
下面为了标中书写看上去舒服，将原数组before 简称 b。
| i | diff （简称：d） | after （简称：a） | sum（简称 s） |
| 0 | = b [ 0 ] | = d [ 0 ] = b [ 0 ] | = a [ 0 ] = d [ 0 ] = b [ 0 ] |
| 1 | = b [ 1 ] - b [ 0 ] | = a [ 0 ] + d [ 1 ] = b [ 0 ] + b [ 1 ] - b [ 0 ] = b [ 1 ] | = s [ 0 ] + a [ 1 ] = b [ 0 ] + b [ 1 ] |
| 2 | = b [ 2 ] - b [ 1 ] | = a [ 1 ] + d [ 2 ] = b [ 1 ] + b [ 2 ] - b [ 1 ] = b [ 2 ] | = s [ 1 ] + a [ 2 ] = b [ 0 ] + b [ 1 ] + b [ 2 ] |
| 3 | = b [ 3 ] - b [ 2 ] | = a [ 2 ] + d [ 3 ] = b [ 2 ] + b [ 3 ] - b [ 2 ] = b [ 3 ] | = s [ 2 ] + a [ 3 ] = b [ 0 ] + b [ 1 ] + b [ 2 ] + b [ 3 ] |
当我们需要从下标 0 加上x， 下标 2 减去 y，可得到以下效果。
下面为了标中书写看上去舒服，将原数组before 简称 b。
| i | diff （简称：d） | after （简称：a） | sum（简称 s） |
| 0 | = b [ 0 ] + x | = d [ 0 ] = b [ 0 ] + x | = a [ 0 ] = d [ 0 ] = b [ 0 ] + x |
| 1 | = b [ 1 ] - b [ 0 ] | = a [ 0 ] + d [ 1 ] = b [ 0 ] + x + b [ 1 ] - b [ 0 ] = b [ 1 ] + x | = s [ 0 ] + a [ 1 ] = b [ 0 ] + x + b [ 1 ] + x = b [ 0 ] + b [ 1 ] + 2 * x |
| 2 | = b [ 2 ] - b [ 1 ] - y | = a [ 1 ] + d [ 2 ] = b [ 1 ] + x + b [ 2 ] - b [ 1 ] - y = b [ 2 ] + x - y | = s [ 1 ] + a [ 2 ] = b [ 0 ] + b [ 1 ] + 2 * x + b [ 2 ] + x - y = b [ 0 ] + b [ 1 ] + b [ 2 ] + 3 * x - y |
| 3 | = b [ 3 ] - b [ 2 ] | = a [ 2 ] + d [ 3 ] = b [ 2 ] + x - y + b [ 3 ] - b [ 2 ] = b [ 3 ] + x - y | = s [ 2 ] + a [ 3 ] = b [ 0 ] + b [ 1 ] + b [ 2 ] + 3 * x - y + b [ 3 ] + x - y = b [ 0 ] + b [ 1 ] + b [ 2 ] + b [ 3 ] + 4 * x - 2 * y |
由此，当我们需要求[ l, r ] 之间的数据 + x的时候，我们只需要 diff [ l ] + x, diff [ r ] - x，就可以达到效果了。