@AC君，因为某些原因本帖写的比前两篇差一点，看看能不能加精
本帖主讲前缀和。
直接开始，话不多说：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前缀和的基本概念：
前缀和算法它主要是用来求区间和的。比如说求从 aia_iai 到 aja_jaj 之间所有的元素总和。记得某大佬说过一句话（忘了在哪了,好像是帅童说的，如有意见可删）：
> 诶这不是一个for循环就解决了吗？
> 我去咋全超时了？
这里的for循环是指直接暴力求区间和，前缀和算法也是需要for循环的。
前缀和就是通过构建前缀和数组来使查询时间复杂度为 O(1)O(1)O(1) 的算法。
拿个题目来举例：
这道题我们可以明显看出数据范围高达 10510^5105 ，而暴力破解的时间复杂度约为 O(nm)O(nm)O(nm) ，单次查询时间复杂度约为 O(n)O(n)O(n) ，正常情况下绝对TLE，只不过神奇的是这题暴力居然能过。
先给出暴力代码：恭喜你找到了本帖的彩蛋：本帖写的很烂，欢迎白嫖\color{white}恭喜你找到了本帖的彩蛋：本帖写的很烂，欢迎白嫖恭喜你找到了本帖的彩蛋：本帖写的很烂，欢迎白嫖
可以看出数据但凡强一点他就TLE了。所以我们要优化这段代码。考虑使用前缀和。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前缀和讲解：
先来看看直接查询：
假设数组是 1,2,3,4,51,2, 3 ,4 ,51,2,3,4,5 ，有3轮查询，分别下标（从1开始）为：
1,51,5 1,5
2,42,4 2,4
3,53,5 3,5
那么手动查询的过程就是（这里的图片就一笔带过了，不做说明）：
可以看出我们每一次查询都进行了一个从 lll 到 rrr 的一次 for 循环，不难发现，代码的时间复杂度极高。所以我们使用前缀和来优化该代码：
还是上边的样例，首先我们构建前缀和数组：
@AAA逃离森林湖的蔡锡龙批发提供的图片：
这里可以发现，当你想要查询一段区间的总和时，例如样例2的 2,42,42,4 。我们只需要用区间为 1,41 , 41,4的数字总和减去区间为 1,11 , 11,1 的数字总和，就可以得到。而我们构建了前缀和数组， 区间 1,41 , 41,4的区间和其实就是 a4a_4a4 ，而区间为 1,11 , 11,1 的数字总和就是 a1a_1a1 。所以我们只需要用 a4a_4a4 的值减去 a1a_1a1 的值即可。以此类推，如果我们需要查询区间 n,mn , mn,m 的总和，我们只需要使用前缀和数组中的 ama_mam 减去 an−1a_{n-1}an−1 即可。代码实现就是
a[m]-a[n-1] 。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码分析：
首先构建前缀和数组，这里把他混在输入中了.由于这里没有什么多余的操作，所以直接覆盖在原数组上即可。注意需要提前渲染一下 a0a_0a0 为 0 或者提前输入 a1a_1a1 ：
之后循环输入查询的左区间，右区间：
输出的话按照上边的公式，在这里就是 sz[r]-sz[l-1] ：
完整代码：
那么本帖也就结束了（找一找彩蛋）谢谢大家观看。
