什么是前缀和

定义

前缀和（Prefix Sum）：对于一个给定的数列 \(a\), 它的前缀和数列 \(sum\) 是通过递推能求出来得 \(sum_i=\sum_{j=1}^{i}a_j\) 部分和。
也就是指某一序列的前 \(n\) 项和。

感性理解

其实前缀和的意思就是对于给定的数组 \(a=[1,2,3,4]\)，他的前 \(i\) 项和 \(sum_i\) 就表示数组中 \(a_0-a_i\) 的和，具体为：

• sum_0=a_0$
• \(sum_1=a_0+a_1\)
• \(sum_2=a_0+a_1+a_2\)
  \(……\)
• \(sum_i=a_0+a_1+...+a_i\)

一维前缀和

定义

顾名思义，一维前缀和就是基于一位数组的前缀和
通过观察上面的式子，我们也会神奇的发现：
\(sum_i=sum_{i-1}+a_i\)

• \(Tips:\) 数组的下标都是从 \(1\) 开始的 \(!\)

作用

可以在O(1)时间情况下快速的求出任一区间[l,r]内的元素之和。