变长子数组求和

题目

给你一个长度为 n 的整数数组 nums 。对于 每个 下标 i（0 <= i < n），定义对应的子数组 nums[start ... i]（start = max(0, i - nums[i])）。

返回为数组中每个下标定义的子数组中所有元素的总和。

子数组 是数组中的一个连续、非空 的元素序列。

第一次解题（暴力法

  sum = 0
        n = len(nums)
        for i in range (n):
            start = max (0,i-nums[i])
            for j in range(start,i+1):
                sum += nums[j]
        return sum

第二次改进（前缀和

1. 先构造前缀和数组 prefix_sum[i] = nums[0] + … + nums[i-1]，从开头到第 i-1 个元素的总和。
2. 想计算区间 nums[l … r] 的总和，它可以通过两个前缀和的差值求得：sum(nums[l … r]) = prefix[r + 1] - prefix[l]
3. 每次查询 nums[start…i] 的和 = prefix[i + 1] - prefix[start]，O(1) 查询。

 n = len(nums)
        prefix = [0] * (n+1)

        for i in range (n):
            prefix[i+1] += prefix[i] + nums[i]
        total = 0
        for i in range(n):
            start = max (0,i-nums[i])
            total += prefix[i+1]-prefix[start]
        return total