微分数组问题背景如果给你一个包含5000万个元素的数组，然后会有频繁的区间修改操作，那么什么是频繁的区间修改操作？比如从第一个数到第1000万个数，每个数加1，这个操作很频繁。此时你应该做什么？很容易想到，从第1个数开始，遍历到第1000万个数，然后对每个数加1，如果这种操作非常频繁，那么在一些实时的时候就会用到这种暴力的方式了。系统可能会被拉伸。于是，今天的主角就出现了——异阵。微分数组的原理比如我们现在有一个数组d，d={0,2,5,4,9,7,10,0}index01234567d[i]025497100那么什么是微分数组呢？其实差分数组本质上也是一个数组。我们暂时将差值数组定义为d。差分数组f的大小与原数组d的大小相同，且f[i]=d[i]-d[i-1]（i≠0）。这是什么意思？是原数组中位置i的元素与位置i-1的元素之差，得到的值就是d[i]的值。因此，示例中arr数组对应的差分数组值如下图所示。index01234567d[i]025497100f[i]023-15-23-10那么构造这样一个东西有什么用呢？是不是浪费宝贵的内存空间？嗯，确实浪费了宝贵的内存，但是却改变了时间的效率。现在我们有这样一个区间修改操作，即在区间1~4中，所有的值都加3。index01234567d[i]02+35+34+39+37100f[i]02+33-15-2-33-10由上表可知，不能傻傻的遍历arr数组的[1,4]范围，然后对每个值加3，这时候只要改变差分数组d即可.显然，[2,4]范围内的差分数组d的值不需要改变，只需要改变差分数组的位置1和位置5的值，即f[1]=f[1]+3，f[5]=f[5]-3，其余不变，为什么呢？因为差分数组的定义-f[i]=d[i]-d[i-1]现在，我们如何根据差分数组f推断出d中某个位置的值呢？比如此时我们想知道d[1]的值，我们不能直接通过d[1]得到原始值，因为我们在区间修改操作中没有修改过d的值，所以必须从前向后遍历递归，由于f[0]=d[0]-0（我们定义d[0]前面的个数为0），则d[0]=f[0]+0，又因为f[1]=d[1]-d[0]=5，则d[1]=5+f[0]。以此类推，由于f[2]=d[2]-d[1]，所以d[2]=3+f[1]。差分数组定义对于已知有n个元素的离线序列d，我们可以创建一个差分数组f，记录每一项与前一项的差分，显然：$$f[i]=\begin{cases}d[i];(i=0)\\d[i]-d[i-1];(1<=i
