题目描述
思路解析动画文字版
题目说要处理多个查询，这就是提示：可以把重复计算提前到初始化阶段。
prefix[0]=0 是哨兵位。它让从 0 开始的区间也能用同一个公式，不需要单独写 if left==0。
初始化：prefix[0] = 0：第二行是 prefix 数组。第 0 格先放 0，意思是“前 0 个数的和”。
加入 nums[0] = -2：第一行第 1 列对应 nums[0]。把它加到上一格 prefix[0] 上，得到 prefix[1]。
加入 nums[1] = 0：prefix[i] 永远表示前 i 个数的和，所以 prefix[2] 覆盖 nums[0..1]。
加入 nums[2] = 3：到这里，nums[0..2] 的和已经存在 prefix[3] 里，后面查询 [0,2] 会直接用它。
继续加入 nums[3] = -5：数组里有负数也没关系，前缀和照样只是普通加法。
加入 nums[4] = 2：初始化阶段只顺序扫一遍 nums，每个元素只处理一次。
加入 nums[5] = -1，前缀数组完成：最终 prefix=[0,-2,-2,1,-4,-2,-3]。构造函数结束后，所有查询都只看这张表。
查询 sumRange(0, 2)：要求 nums[0..2]，右边界要变成 right+1，所以取 prefix[3]；左边界之前没有元素，所以减 prefix[0]。
查询 sumRange(2, 5)：prefix[6] 是 nums[0..5] 的总和；减掉 prefix[2]，就把 nums[0..1] 切掉，只剩 nums[2..5]。
查询 sumRange(0, 5)：从 0 开始的区间也不用特殊处理，因为 prefix[0]=0 正好代表“左边没有要切掉的数”。
这题把“多次区间查询”变成了“初始化多做一点、查询少做很多”。
参考代码
class NumArray: def __init__(self, nums): self.prefix = [0] for x in nums: self.prefix.append(self.prefix[-1] + x) def sumRange(self, left, right): return self.prefix[right + 1] - self.prefix[left]复杂度
- 初始化时间：O(n)，构造 NumArray 时扫描 nums 一次，建立 prefix。
- 单次查询时间：O(1)，sumRange 只读取 prefix[right+1] 和 prefix[left]。
- 空间复杂度：O(n)，额外保存长度为 n+1 的前缀和数组。
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
寻找数组的中心下标
LeetCode 724 · 简单 · 沿着 前缀和套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题