前缀和python代码

前缀和（Prefix Sum）是一个数据结构技术，主要用于高效地计算某个区间内元素的和，通常用于解决与数组子段和相关的动态规划问题。在Python中，你可以用列表或数组来实现前缀和。

以下是一个简单的Python代码示例：

def prefix_sum(arr):
    # 初始化前缀和为数组本身
    prefix_sum_array =  + arr
    # 计算累加和并更新前缀和数组
    for i in range(1, len(arr) + 1):
        prefix_sum_array[i] += prefix_sum_array[i-1]
    return prefix_sum_array

# 测试例子
arr = [1, 2, 3, 4, 5]
print("原始数组:", arr)
print("前缀和数组:", prefix_sum(arr))

当你需要查询区间 `[i, j)` 的元素之和，只需要从 `prefix_sum_array[j]` 中减去 `prefix_sum_array[i-1]` 即可，这将非常快速，时间复杂度为 O(1)。