第十一课-前缀和

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

定义

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

计算前缀和

    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    f = [0] * n
    f[0] = a[0]
    for i in range(1, n):
        f[i] = f[i-1] + a[i]

为什么需要前缀和？

场景一

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

场景二：快速计算区间和

5
1 2 3 4 5

对于区间(l,r)，用s(l,r)表示区间(l,r)的所有元素和，用s(i)表示前i个数的和，下标都是从1开始。

• s(3,5)=s(5)-s(2)
• s(3,4)=s(4)-s(2)

我们可以得到下面的公式：s(l,r) = s(l)-s(r-1)

s(i)数组可以在O(n)的时间内算出来，所以有了s(i)数组后，我们可以在O(1)的时间内算出任意区间(l,r)元素的总和。

练习题

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