第十一课-前缀和

参考：https://oi.wiki/basic/prefix-sum/

定义

前缀和可以简单理解为「数列的前 n 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。

为什么需要前缀和？

• 有一个长度为n（n<=10000）的数组a，计算前k项和的时间复杂度是多少？
• 如果查询有k(k<=10^5)次，总时间复杂度是多少？
  • 能不能优化？

练习题

前缀和：http://oj.oldmoon.cn/p/991 (这个题目用前缀和思路，拿到70分即为正确！）