Range Sum Query
你会得到一个不会改变的整数数组 nums 和一个 queries 列表。每个查询都是一对从 0 开始的索引 [left, right]，它要求计算 nums[left] + nums[left+1] + ... + nums[right]，左右两端都包含在内。按查询的相同顺序返回答案。
函数
- numsinteger-array
- 每次查询都相同的整数数组
- queriesinteger-2d-array
- 要相加的区间，每个区间都是一对 [left, right]，其中 left ≤ right
- 返回值integer-array
- 每个范围的总和，每个查询对应一个，并按查询顺序排列
约束条件
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.length对于每个查询[left, right]
示例
- 输入
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- 输出
- [6, 0, 1]
- 解释
- 索引 0 到 2 中的值之和为
3 + (-2) + 5 = 6。索引 1 到 4 中的值之和为-2 + 5 + 1 + (-4) = 0。范围[3, 3]中只有一个值：1。
- 输入
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- 输出
- [18, 9, 2, 8]
- 解释
- 整个数组的总和是
18，最后两个值的总和是1 + 8 = 9，索引 0 处的值是2，索引 1 到 2 处的值的总和是7 + 1 = 8。
进阶
如果这些数字组成一个网格，并且每次查询都要求计算一个矩形区域的总和，你会如何扩展前缀和，以便在常数时间内回答每次查询？
提示
逐个打开提示，每个都会多透露一点。
很多查询涉及的值几乎相同。你可以在读取任何查询之前，先完成哪些工作？
如果你知道每个
i对应的前i个值的总和，那么一个范围的总和就是其中两个总和的差。用
prefix构建前缀和，令prefix[0] = 0且prefix[i+1] = prefix[i] + nums[i]。然后，每个查询[left, right]的结果是prefix[right+1] - prefix[left]。
题解
单个范围就是一个循环，但每个查询都可能覆盖数组的大部分元素，因此分别求和会重复进行相同的加法。先将数组累加一次，得到前缀和，这样每个范围都只需要做一次减法。
将每个范围的数值相加
结果正确，但无法在最大的测试中运行完毕
思路
对于每个查询，将 nums[left] 到 nums[right] 的值加到总和中。这样做是正确的，因为它会读取范围内的每个值，而且对于单个查询，这已经是最好的方法。一个查询最多可能包含 n 个值，因此 q 个查询最多需要进行 n × q 次加法：当 n = 10^4 且 q = 1500 时，需要进行 1.5 × 10^7 次加法，其中几乎所有值都会被重复计算。
算法
- 创建一个空的答案列表。
- 对于每个查询
[left, right]，设置total = 0。 - 将从
left到right（包含两端）的每个nums[i]加到total中。 - 将
total追加到答案中，并在最后一个查询完成后返回答案。
def sumRange(nums, queries):
answers = []
for left, right in queries:
total = 0
for i in range(left, right + 1):
total += nums[i]
answers.append(total)
return answers前缀和
思路
令 prefix[i] 表示前 i 个值的和，其中 prefix[0] = 0。对于 [3, -2, 5, 1, -4, 6]，得到 [0, 3, 1, 6, 7, 3, 9]。
范围 [left, right] 的和等于截至索引 right 的所有值之和，减去索引 left 之前的所有值之和：prefix[right+1] - prefix[left]。对于 [1, 4]，结果是 prefix[5] - prefix[1] = 3 - 3 = 0。开头的 0 让从索引 0 开始的范围也能使用同一个公式。只需遍历一次，进行 n 次加法即可构建数组，而每次查询只需进行一次减法。
算法
- 创建长度为
n+1的prefix，并设置prefix[0] = 0。 - 对于从
0到n-1的每个i，设置prefix[i+1] = prefix[i] + nums[i]。 - 对于每个查询
[left, right]，将prefix[right+1] - prefix[left]添加到答案中。 - 返回答案。
def sumRange(nums, queries):
# prefix[i] is the sum of the first i values, so prefix[0] = 0.
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
# nums[left..right] is the first right+1 values minus the first left values.
return [prefix[right + 1] - prefix[left] for left, right in queries]
易错点和边界情况
- 写成
prefix[right] - prefix[left]。由于prefix[0] = 0，这样会漏掉nums[right]，所以范围[3, 3]得到的结果是0，而不是1。 - 让
prefix和nums一样长，这样prefix[i]就包含nums[i]。从 0 开始的范围需要用到prefix[-1]，但它超出了范围，而 Python 会静默地读取最后一项。 - 在暴力循环中使用
i < right作为结束条件。范围的两端都包含在内，因此[3, 3]不会累加任何值。 - Lua 和 R 从 1 开始计数，因此，0 起始的查询范围
[left, right]覆盖nums[left+1]到nums[right+1]，前缀索引也会以相同的方式偏移。
常见问题3
什么是前缀和数组？
一种数组，其中每个元素都是某个位置之前所有值的总和：prefix[i] = nums[0] + ... + nums[i-1]，其中 prefix[0] = 0。你可以遍历一次来构建它，然后任意范围 [left, right] 的和就是 prefix[right+1] - prefix[left]。
使用前缀和进行范围求和查询的时间复杂度是多少？
构建前缀数组需要一次 O(n)，之后每次查询需要 O(1)，因此 q 次查询总共需要 O(n + q)。直接累加每个范围的值，每次查询最多需要 O(n)，总共需要 O(n·q)。
如果数组在查询之间发生变化，会怎么样？
这时，前缀数组就不合适了，因为一次更新会改变它之后的所有总和，修复需要 O(n) 的时间。树状数组或线段树可以在 O(log n) 的时间内处理更新和区间求和。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def sumRange(nums, queries):
# 在这里编写代码测试 #1
测试 #2
参数
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
预期输出
[6, 0, 1]