我们从问题入手。
入门问题：有已赋值的 n 个数，现在有 m 个指令
操作 1： 每一次要求将第 k 个数加上 a，最后求所有数的值；
操作 2： 查询第 k 个数字的值。
$1 ≤ k ≤ n ≤ 10^5$
这一题其实用一个数组就可以维护。
问题一：有已赋值的 n 个数，现在有 m 个指令，每一个指令要求查询第 x 个数到第 y 个数的和。
$1 ≤ x ≤ y ≤ n,m ≤ 10^5$
如果暴力求和是会 TLE 的。
那应该如何解决这个问题呢？
这就要引出前缀和了。
可以看出，$\sum_{i=x}^ya_i = \sum_{j=1}^ya_j - \sum_{k=1}^{x-1}a_k$
所以我们只需要求第一个数到各个数的和即可。
求这些数很容易，O(n) 复杂度递推，接下来就可以 O(1) 查询了。
问题二：有已赋值的 n 个数，现在有 m 个指令，每一次要求将第 x 个数到第 y 个数加上 a，最后求所有数的值。
$1 ≤ x ≤ y ≤ n,m ≤ 10^5$
其实这题分块、线段树、树状数组以及其它的很多算法都可以过这题。
但是请看下一个问题：
问题三：有已赋值的 n 个数，现在有 m 个指令，每一次要求将第 x 个数到第 y 个数加上 a，最后求所有数的值。
$1 ≤ x ≤ y ≤ n,m ≤ 5*10^6$
我们发现：这个 5e6 的范围太大了，O(n log n) 以及更慢的复杂度是过不了的。
所以，下一个内容是：
① 什么是差分？
差分，就是一个通过常数复杂度的标记实现求和及询问的一种技巧。
一般适合静态维护（前面先加，最后求值）。
② 差分怎么用？
我们马上举一个例子：
有一个数列：
1 9 2 8 3 7 4 6 5
tag: 0 0 0 0 0 0 0 0 0 // 现在还没有打上标记
现在，我们将第 3 个数到第 5 个数加上 2.
那我们就发现，可以把第 3 个数开始把后面所有的数加上 2，再从第 6 个数开始把后面所有数减去 2 呢，就相当于把第 3 个数到第 5 个数加上 2 了。
然后这么标记：
a[i]: 1 9 2 8 3 7 4 6 5 tag : 0 0 2 0 0 -2 0 0 0 // 打上标记*1
然后，我们再将第 4 个数到第 8 个数减去 1.
按照上面的想法，我们可以从第 4 个数开始把后面所有的数减去 1，在从第 9 个数开始把后面所有的数加上 1.
a[i]: 1 9 2 8 3 7 4 6 5 tag : 0 0 2 -1 0 -2 0 0 1 // 打上标记*2
假设指令执行结束，那么我们这样求和：
用一个 sum 数组记录，$sum_i$ 代表前 i 个数所带的 tag 的和。
a[i] : 1 9 2 8 3 7 4 6 5 tag : 0 0 2 -1 0 -2 0 0 1
sum[i] : 0 0 2 1 1 -1 -1 -1 0
最后，我们把 $a_i$ 加上对应的 $sum_i$ 相加，就是答案了。（这里有用到前缀和的思想）
时间复杂度 O(n).
与其说这是一个算法，不如说这是一个思想。
我们会碰到很多这样的题目，看似需要比较复杂的数据结构，其实很简单。
这需要我们灵活运用所学的知识。
原文：https://www.cnblogs.com/zengpeichen/p/11279207.html