前缀和与差分
解决的问题
现在有nnn个数字,使用a1,a2,a3...ana_1,a_2,a_3...a_na1 ,a2 ,a3 ...an 来表示。
并且有qqq次提问，每一次提问求解范围[l,r][l,r][l,r]，也就是第lll到第rrr个数字总和为多少。
伪代码:
这段代码固然可以解决这个问题，但是呢，如果我们的数字数量和提问次数，到达10610^6106的级别，这时候，由于该段代码的时间复杂度为O(n∗q)O(n * q)O(n∗q)，最终计算次数可能会到达101210^{12}1012，而计算机在一秒当中计算的次数大约在10810^8108次，因此这样写，会导致时间超限。
所以，我们要思考，有什么方法，可以让程序运行时间变短的同时，然后还能保证答案的正确性。
而这样的方法，我们会把他称之为算法。
前缀和
前缀和是通过创建范围1到任意数字的数值总和的数组，来解决这个问题的。
在这里，我们可以把这个数组称之为是sum数组, 因为它保存了从1到任意数字的数值总和。
当你需要求解范围[l,r][l,r][l,r]的数值总和时，只需要计算sum[r]减去sum[l-1]即可。
每一次求解范围数值，时间复杂度皆为O(1)O(1)O(1)，也就是一次减法即可，构建加单次查询的时间复杂度为O(n)O(n)O(n)，而前缀和的构建时间复杂度为O(n)O(n)O(n)，所以总的时间复杂度为O(n)O(n)O(n)。
参考代码
差分
差分是前缀和的一种变形，它可以帮助我们解决一些区间加减的问题
模版
