前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身）。前缀和分为一维前缀和，以及二维前缀和。前缀和是一种重要的预处理，能够降低算法的时间复杂度。
前缀和、前缀积也称前缀和数组、前缀积数组。除了前缀和，还有后缀和、前缀积、后缀积
给一数组 A：
- 前缀和：新建一数组
B，数组中每一项B[i]保存A中[0...i]的和；- 后缀和：新建一数组
B，数组中每一项B[i]保存A中[i...n-1]的和；- 前缀积：新建一数组
B，数组中每一项B[i]保存A中[0...i]的积；- 后缀积：新建一数组
B，数组中每一项B[i]保存A中[i...n-1]的积；
一维前缀和的公式：
sum[i] = sum[i - 1] + arr[i];
说明：
sum 是前缀和数组arr 是内容数组拥有前缀和数组后, 我们可以在
[i, j] 的区间和公式:
interval[(i, j)] = sum[j] - sum[i - 1];