差分是一种处理数据巧妙而简单的方法，可以应用于区间修改和询问问题。例如，将给定的数据集合 A 分成很多区间，并对这些区间进行很多次操作，每次都是对某段区间内的所有元素做相同的加减操作，此时若一个个的遍历修改这段区间内的每个元素，就会非常的耗时，效率不高。为此，我们引入一个叫 “ 差 分 数 组 ” color{Orange}“差分数组” “差分数组” B，当修改这段区间时，只需要对这段区间的 端 点 color{Purple}端点 端点 进行修改，就能将整段区间的元素修改，这个操作是非常平滑的，只需要 O（1） 的复杂度。当我们将所有修改操作进行完毕后，再利用差分数组，即可计算出新的数据集合 A。
对于集合 A，它可以是一维的线性数组 a[ ]，二维矩阵 a[ ] [ ]， 三维立体 a[ ] [ ] [ ] 。与之对应的，差分数组 B[ ] ，B[ ] [ ] ，B[ ] [ ] [ ] 。当然如果想象力足够的话四维也是有可能的。
1. 一维差分 1.1 基本概念问 题 描 述 color{Turquoise}问题描述 问题描述：给定一个长度为 n 的一维数组 a[ ]，数组内的每个元素都有初值，并对其进行一下操作：
（1）修改操作：进行 m 次区间修改，每次修改对这段区间【L，R】内的所有元素做相同的加减操作。
（2）查询操作：查询某个元素的值是多少
~~~~ 如果简单的暴力遍历，那么对于每次的修改复杂度是 O（n） 的，有 m 次修改，此时复杂度为 O(n*m) ，如果用差分法的话，复杂度将为 O(n + m)
原理
~~~~ 对于这个原数组 a[ ] = {a1，a2，a3，···，an}，我们构造出这样一个数组 B[ ] = {b1，b2，b3，···，bn}，使得 ai = b1 + b2 + ··· + bi，那么b[ ] 就称为 a[ ] 的差分，a[ ] 称为 b[ ] 的前缀和。可以发现，差分与前缀和是一组逆运算。
~~~~ 如何利用差分数组对区间进行修改呢？为什么利用差分数组能提升修改的效率呢？
1. 区 间 修 改 color{Purple}区间修改 区间修改，时间复杂度为 O（1）
现在要将原数组 a[ ] 区间【L，R】上的每个数都加上一个 c，如下图所示：
第一个受到影响的差分数组中的元素为 bL]，所以 b[L] += c ，对于 a[L] 后面的数都会受到 B[L] 的影响加上 c。最后一个受影响的差分数组中的元素b[R]，为了保证不影响到 R 后面的元素，所以我们需要 b[R + 1] -= c。也就是说，对于 a[x] = b[1] + b[2] + ···+ b[x]，利用差分数组能够精确地实现只修改指定区间内元素的目的，而不会修改区间外的a[ ] 的值，也就是：
(1) 1 ≤ x < L, 前缀和 a[x] 不变。(2) L ≤ x ≤ R, 前缀和 a[x] 加上了 c 。(3) R < x ≤ N, 前缀和 a[x] 不变，因为被 b[R + 1] 中的c抵消了。这样一来，就不必每次都对区间内所有的数进行处理，只需要修改区间【L，R】的两个端点 b[ ] 的值即可，复杂度是 O(1) 的。
void add(int l, int r, int c){ b[l] += c; b[r + 1] -= c;}2. 单 点 查 询 color{Purple}单点查询 单点查询，时间复杂度为 O（n）
~~~~ 根据定义，差分数组 b[ x ] 的前缀和 b[1] + b[ 2 ] + ··· + b[ x ] 就是原数组 a[x] 的值
void get(int x){ for(int i = 1; i