前缀和知识笔记

使用场景

当一个数组需要频繁计算某个区间内的元素和，推荐使用前缀和，可以避免每一次计算都把整个区间的元素遍历一遍。

生成前缀和数组

假设前缀和数组为prefix_arr，prefix_arr的第一个元素与原数组的第一个元素相同，之后每一个元素值都等于本身加上前一个元素，即：
prefix_arr[i] = prefix_arr[i] + prefix_arr[i - 1]

使用前缀和数组

假设前缀和数组为prefix_arr，其中prefix_arr[i]表示前i个元素（包含i）的和，如果需要计算区间[j, i]的元素和SUM(j, i)，其中0 < j <= i，则：
SUM(j, i) = prefix_arr[i] - prefix_arr[j - 1]

Python代码

def prefix_sum(arr: list):n = len(arr)prefix_arr = [0] * n  # 前缀和数组prefix_arr[0] = arr[0]for i in range(1, n):prefix_arr[i] = prefix_arr[i] + prefix_arr[i - 1]return prefix_arr