【前缀和】1588. 所有奇数长度子数组的和

**前缀和**

前缀和是一种常见的算法技巧，用于快速计算一个数组中所有子数组的和。它通过预先计算每个位置的前缀和来实现，这样就可以在 O(1) 的时间复杂度内计算任意子数组的和。

**定义**

假设我们有一个长度为 n 的数组 `arr`，其中 `n >=0`。前缀和 `prefix_sum[i]` 定义为从下标0 到 i 的所有元素之和：

prefix_sum[i] = arr[0] + arr[1] + ... + arr[i]

**计算前缀和**

我们可以使用以下公式计算前缀和：

prefix_sum[i] = prefix_sum[i-1] + arr[i]

这意味着我们只需要在每次迭代中更新 `prefix_sum` 的值，而不需要重新计算所有元素的和。

**示例代码**

下面是 Python代码，演示了如何使用前缀和来快速计算一个数组中所有子数组的和：

def calculate_prefix_sum(arr):
 n = len(arr)
 prefix_sum = [0] * (n +1) # 初始化前缀和数组 # 计算前缀和 for i in range(n):
 prefix_sum[i+1] = prefix_sum[i] + arr[i]

 return prefix_sum# 测试数据arr = [3,5, -2,8,4, -1]
prefix_sum = calculate_prefix_sum(arr)

print("前缀和:", prefix_sum)

**输出**

前缀和: [0,3,8,6,14,13,12]

如上所示，`prefix_sum` 数组包含从下标0 到每个位置的所有元素之和。

**使用前缀和**

现在，我们可以使用 `prefix_sum` 数组来快速计算任意子数组的和。例如，要计算从下标2 到4 的子数组的和，我们只需要取 `prefix_sum[5] - prefix_sum[2]`：

sub_array_sum = prefix_sum[5] - prefix_sum[2]
print("从下标2 到4 的子数组之和:", sub_array_sum)

**输出**

从下标2 到4 的子数组之和:14

如上所示，使用前缀和，我们可以快速计算任意子数组的和。

**总结**

在本文中，我们介绍了前缀和算法技巧，并提供了 Python代码示例。通过预先计算每个位置的前缀和，我们可以在 O(1) 的时间复杂度内计算任意子数组的和。这使得前缀和成为一个非常有用的工具，特别是在需要快速计算大量数据时。

**参考**

* [Wikipedia: Prefix sum]( />* [GeeksforGeeks: Prefix Sum Array](