04. 构建前缀和

正文

以下是一个前缀和算法的常见模板：

fun prefixSum(nums: IntArray): IntArray {
    val prefixSum = IntArray(nums.size + 1)

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

在这个模板中，我们使用一个额外的数组 prefixSum 来存储原始数组 nums 的前缀和。通过遍历原始数组，我们可以计算每个位置的前缀和并存储在 prefixSum 中。

使用前缀和数组 prefixSum，我们可以高效地回答多个查询，例如计算某个区间的和。假设我们需要计算区间 [left, right] 的和，我们可以使用如下方式获取结果：

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

这个计算结果即为原始数组中从位置 left 到位置 right 的元素之和。
请注意，在模板中，前缀和数组 prefixSum 的长度比原始数组 nums 的长度多了一个元素。这是为了方便计算区间和时的边界情况。