笔记

4小时后开始周赛，双周赛依旧稳定两题，第三题用例全过，但是超时了，但是学到了新知识差分，感觉很神奇。

原数组a的差分数组是[a1,a2-a1,a3-a2...]

人话就是，每一个位置都是当前位置和前一个位置的差值，所以原数组的信息不会丢失。

其实还是有信息丢失的，差分数组要还原的话依赖于顺序，是顺序提供了额外的信息。

然后神奇的地方来了，当对原数组某个区间的元素执行加减操作时，这个操作体现在差分数组上就只是b[l]+x,b[r+1]-x(b是差分数组……

Why?这很好证明，因为(l,r)的元素都是原数组里两个数的差值，这两个数同时加上或减去一个数，并不改变结果。

我理解了，我震惊了。这是哪个天才想出来的，太优雅了，变化了的信息只在两个位置存储，还原的时候是计算前缀和，实际上是等于某个位置的元素在给其它位置的元素提供信息，用这种方式把冗余的部分优化掉了。

它的底层思想，就是在去除重复的部分。这就是我做T3时一直在寻找的东西，既然每一个位置都是一样的变化，那我为什么非要真的在每个位置都执行操作，能不能用某种方式只记录变化的区间？我没想出来，但是这种方式真的存在！

有点熟悉。字典树也是把重复部分提取出来，动态规划也是把重复的计算优化……

好像窥探到一点点算法的本质了。