2022.3.8 差分
不知不觉，这么长时间过去了，重新开始刷题了，今天来看一下差分的方法。
1109. 航班预订统计
这道题其实之前也做过，但是再一次看到的时候还是只能想到暴力方法，与之前一模一样超时了，晕。仔细看了看题解，原来要使用差分的方法。所谓差分，就是求前缀和的逆向操作。通过不断对数组的区间进行修改，最终可以获得一个前缀和数组。在这题中，每次对于一段时间内的数组进行增加操作，除了使用暴力方法以外，我们可以使用差分将时间复杂度减小到O(1)。
那么具体差分的方法：
对于区间[l,r]整体增加一个值v
我们可以在区间左侧对于c[l] += v，这样相当于对于从l开始的数组所有数都加上一个值v。
然后对c[r+1] -= v，由于我们只需要在[l,r]范围内对所有值加v，所以在这一段区间结束之后需要再将加上的值减掉，这样相当于抵消了之前+v的影响。也可以理解为：对从r+1开始的数组所有值-v，这样从c[r+1]开始所有的值先加了v后减了v，相当于没有变化。如果r+1大于了数组长度n，就不用管了。
这样，对于所有的区间操作结束之后，我们就会获得一个前缀和数组，然后就可以对数组进行各种操作了。
798. 得分最高的最小轮调
这题同样也使用了差分的方法，首先对于数组中每个数分析，得到对于每个数来说可以得分的范围。经过分析根据每个数x与下标i的大小可以有两种情况：
第一种得到的k在[i+1, i-x+n]内，所以只需要将数组[i+1]加一，[i-x+n]减一就可以了。
对于第二种情况，k在[0, i-x]和[i+1, n-1]内，同样也对于[i+1]加一，[i-x]减一，但是这时由于i-x < i+1， 相当于我们只在i+1后面的值加了一，而对于[0, i-x]，我们只在i-x减了一，所以需要在[0]处额外加一，这样才相当于对两个区间都进行了加一操作。
