04. 构建前缀和

正文

前缀和（Prefix Sum）是一种非常重要的预处理技巧，主要用于高效计算数组中任意区间的元素之和。

算法模板

fun prefixSum(nums: IntArray): IntArray {
    // 前缀和数组长度为 n + 1，prefixSum[i] 表示 nums 中前 i 个元素的和
    val prefixSum = IntArray(nums.size + 1)

    // 计算前缀和数组
    for (i in 1..nums.size) {
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1]
    }
    
    return prefixSum
}

使用说明

1. 区间求和：
   使用前缀和数组 prefixSum，我们可以以 $O(1)$ 的时间复杂度回答多个区间和查询。计算区间 [left, right]（包含两端）的元素之和：

   val sum = prefixSum[right + 1] - prefixSum[left]

2. 核心优势：
   将多次区间查询的时间复杂度从 $O(N)$ 降低到 $O(1)$。

3. 注意点：

   • 前缀和数组长度通常设为 n + 1，其中 prefixSum[0] = 0。这样可以统一处理 left = 0 的边界情况，无需额外的 if 判断。
   • 如果数组元素较大，注意前缀和数组可能发生整型溢出，必要时使用 LongArray。