差分：
给出n个数，再给出Q个询问，每个询问给出l，r，x，要求你在l到r上每一个值都加上x，而只给你O(n)的时间范围，怎么办？
Xenny大佬的树状数组详解 - Xenny - 博客园 (cnblogs.com)里利用一个差分值构建的树状数组，可以用来进行区间更新，单点查询。
差分的特点是区间[a,b]加k的话，我只要对差分数组的d[a]+k,d[b+1]-k即可（注意如果b+1>n则d[b+1]不变）
“则有 A[i] = Σij = 1D[j];(D[j] = A[j] - A[j-1])，即前面i项的差值和，这个有什么用呢？例如对于下面这个数组
- A[] = 1 2 3 5 6 9
- D[] = 1 1 1 2 1 3
如果我们把[2,5]区间内值加上2，则变成了
- A[] = 1 4 5 7 8 9
- D[] = 1 3 1 2 1 1
发现了没有，当某个区间[x,y]值改变了，区间内的差值是不变的，只有D[x]和D[y+1]的值发生改变，至于为什么我想我就不用解释了吧。”（转自Xenny）
单点查询上，可以知道A[i]=D[1]+D[2]+....+D[i-1]+D[i]，会使得单点十分好求。
这是线性的差分。
前缀和可以看作给你一个差分数组，你要建立一个原数组。