2023-07-26 LeetCode每日一题（更新数组后处理求和查询）

**2023-07-26 LeetCode 每日一题**

**题目描述**

给定一个整数数组 `nums` 和一个二维数组 `queries`，其中每个子数组 `query[i]` 包含两个元素：一个整数 `left` 和一个整数 `right`。要求你计算出对于每个查询 `query[i]`，在 `nums` 中从下标 `left` 到 `right` 的所有数字的和。

**示例1**

输入：`nums = [1,2,3,4,5], queries = [[1,3],[6,10]]`

输出：`[9,0]`

解释：对于第一个查询 `[1,3]`，从 `nums` 中取出下标为1、2 和3 的数字（即1、2 和3），求和得到9。对于第二个查询 `[6,10]`，由于 `nums` 只有五个元素，因此没有满足条件的数字，返回0。

**示例2**

输入：`nums = [4,5,6,7,8], queries = [[1,3],[2,4]]`

输出：`[15,25]`

解释：对于第一个查询 `[1,3]`，从 `nums` 中取出下标为1、2 和3 的数字（即4、5 和6），求和得到15。对于第二个查询 `[2,4]`，从 `nums` 中取出下标为2、3 和4 的数字（即5、6 和7），求和得到18。

**解决方案**

我们可以使用前缀和数组来解决这个问题。前缀和数组是将原始数组中的每个元素与其左侧所有元素的总和相加而得出的新数组。

class NumArray:
 def __init__(self, nums):
 self.nums = nums self.prefix_sum = [0] * (len(nums) +1)
 for i in range(len(nums)):
 self.prefix_sum[i+1] = self.prefix_sum[i] + nums[i]
 def sumRange(self, left: int, right: int) -> int:
 return self.prefix_sum[right+1] - self.prefix_sum[left]

在这个解决方案中，我们首先计算原始数组的前缀和，然后使用这些前缀和来计算每个查询的和。

**时间复杂度**

时间复杂度为 O(n)，其中 n 是原始数组中的元素数量。我们需要计算原始数组的前缀和，这需要 O(n) 的时间。

**空间复杂度**

空间复杂度为 O(n)，其中 n 是原始数组中的元素数量。我们需要存储原始数组的前缀和，总共需要 O(n) 的空间。

**代码注释**

* `__init__` 方法用于初始化 NumArray 对象。它计算原始数组的前缀和并将其存储在 `prefix_sum` 列表中。
* `sumRange` 方法用于计算从下标 `left` 到 `right` 的所有数字的和。它使用 `prefix_sum` 列表来计算这个和。

**示例代码**

nums = [1,2,3,4,5]
queries = [[1,3],[6,10]]

num_array = NumArray(nums)
print(num_array.sumRange(1,3)) # Output:9print(num_array.sumRange(6,10)) # Output:0nums = [4,5,6,7,8]
queries = [[1,3],[2,4]]

num_array = NumArray(nums)
print(num_array.sumRange(1,3)) # Output:15print(num_array.sumRange(2,4)) # Output:18

在这个示例代码中，我们首先创建一个 `NumArray` 对象，然后使用 `sumRange` 方法来计算从下标 `left` 到 `right` 的所有数字的和。