题目
分析
这道题目是介绍“差分”的概念和应用。之前我们学到的“前缀和”与“差分”有着很密切的关联。
先看“差分”的定义：
对于数组\(a[1, 2, ..., N]\)，我们定义\(diff[i]=a[i]-a[i-1]\)为数组\(a\)的差分数组。1
然后我们看下，根据差分定义我们对差分数组进行前缀和会有怎样的结果：
\(\sum_{k=1}^{n} \mathrm{diff}_k = \sum_{k=1}^{n} (a_k - a_{k-1}) = (a_1-a_0) + (a_2-a_1) + \dots + (a_n-a_{n-1}) = a_n - a_0\)
也就是说，前n项差分数组的和就是原数组的\(a_n\)。
我们用一个简单的数组说明具体说明一下：
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| \(a_i\) | 1 | 1 | 2 | 2 | 1 | 3 | 3 | 5 |
| \(diff_i\) | 1 | 0 | 1 | 0 | -1 | 2 | 0 | 2 |
| \(\sum_{1}^{i}diff_i=a_i\) | 1 | 1 | 2 | 2 | 1 | 3 | 3 | 5 |
再回到本题。如果要对\([x, y]\)之间的数据都加上z，可以只需要两次操作：
- \(diff_x+=z\)
- \(diff_{y+1}-=z\)
这么操作后，只有\([x, y]\)之间的数字被修改。有兴趣的读者可以自行证明。2
同时，针对题意，我们在跟踪最小值的时候，可以直接用\(diff\)数组进行前缀和操作。
答案
思考
差分数组与前缀和数组是基本的数据结构。本题中，本来有n次可能涉及整个区间（n）的操作，时间复杂度会达到\(O(N^2)\)。而通过差分数组（以及前缀和），总共n次操作，每次只要操作两个数据，复杂度大大降低，来到\(O(N)\)。