区域和检索 - 数组不可变 图解题解
这道题到底在问什么
- nums
- [2,4,1,3,5]
- sumRange(1,3)
- 4+1+3 = 8
最优解：一步一步想明白
- 3记住一条公式：区间 [i,j] 的和 = pre[j+1] − pre[i]。pre[k] 是「前 k 个数的和」，预处理一次，查询全靠它。
- 4先给前缀和表放一条 pre[0]=0：还没取任何数时，和是 0。这条是后面减法能对齐的关键。
- 5指针走到下标 0，这一格是 2。把它加到上一个前缀和上，得到新的前缀和。
- 6pre[1] = 前一个前缀和 0 加上 2，等于 2（高亮那行就是刚算出的）。
- 7指针走到下标 1，这一格是 4。把它加到上一个前缀和上，得到新的前缀和。
- 8pre[2] = 前一个前缀和 2 加上 4，等于 6（高亮那行就是刚算出的）。
- 9指针走到下标 2，这一格是 1。把它加到上一个前缀和上，得到新的前缀和。
- 10pre[3] = 前一个前缀和 6 加上 1，等于 7（高亮那行就是刚算出的）。
- 11指针走到下标 3，这一格是 3。把它加到上一个前缀和上，得到新的前缀和。
- 12pre[4] = 前一个前缀和 7 加上 3，等于 10（高亮那行就是刚算出的）。
- 13指针走到下标 4，这一格是 5。把它加到上一个前缀和上，得到新的前缀和。
- 14pre[5] = 前一个前缀和 10 加上 5，等于 15（高亮那行就是刚算出的）。
- 15扫一遍就把前缀和全建好了：pre=[0,2,6,7,10,15]。从现在起，任何区间查询都靠它做一次减法。
- 16来了一个查询 sumRange(1, 3)：求绿色高亮这一段（下标 1 到 3）的和。
- 17套公式：这段的和 = 前 4 个之和 减 前 1 个之和 = pre[4] − pre[1] = 10 − 2。
- 1810 减 2 等于 8。整段不用逐个相加，一次减法就得到答案 8。
- 19来了一个查询 sumRange(0, 4)：求绿色高亮这一段（下标 0 到 4）的和。
- 20套公式：这段的和 = 前 5 个之和 减 前 0 个之和 = pre[5] − pre[0] = 15 − 0。
- 2115 减 0 等于 15。整段不用逐个相加，一次减法就得到答案 15。
- 22来了一个查询 sumRange(2, 4)：求绿色高亮这一段（下标 2 到 4）的和。
- 23套公式：这段的和 = 前 5 个之和 减 前 2 个之和 = pre[5] − pre[2] = 15 − 6。
- 2415 减 6 等于 9。整段不用逐个相加，一次减法就得到答案 9。
⚠️ 容易写错的地方
✗ 错：用 pre[j] − pre[i] 算区间和
✓ 对：用 pre[j+1] − pre[i]
pre[k] 是「前 k 个」，要包含下标 j 这一格，得用 pre[j+1]；少加一会漏掉右端点
✗ 错：前缀和数组从 pre[0]=nums[0] 起，没有 0 这一项
✓ 对：让 pre[0]=0、长度 n+1
没有 pre[0]=0，i=0 的查询就没法对齐减法，要写一堆特判
✗ 错：每次查询现场把区间加一遍
✓ 对：预处理前缀和，查询只做减法
现场加是 O(n)，查询多了会超时；前缀和把单次查询降到 O(1)
完整代码（Python / C++ / Java）
Python
class NumArray:
def __init__(self, nums):
self.pre = [0] # pre[0] = 0
for x in nums: # 预处理前缀和
self.pre.append(self.pre[-1] + x)
def sumRange(self, i, j):
return self.pre[j+1] - self.pre[i] # 一次减法C++
class NumArray {
vector<int> pre;
public:
NumArray(vector<int>& nums) {
pre.push_back(0);
for (int x : nums) pre.push_back(pre.back() + x);
}
int sumRange(int i, int j) { return pre[j+1] - pre[i]; }
};Java
class NumArray {
int[] pre;
public NumArray(int[] nums) {
pre = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++)
pre[i+1] = pre[i] + nums[i];
}
public int sumRange(int i, int j) { return pre[j+1] - pre[i]; }
}复杂度
预处理
O(n)
建前缀和数组，把数组扫一遍
单次查询
O(1)
只做一次减法 pre[j+1] − pre[i]
空间
O(n)
多存一个长度 n+1 的前缀和数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 区域和检索 - 数组不可变 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
前缀和为什么能把查询从 O(n) 降到 O(1)？+
因为区间和被拆成两个前缀和之差。前缀和一次预处理就全算好了，查询时不再逐个累加，只做一次减法，所以是 O(1)。
如果数组会被修改（某个元素变了）还能用前缀和吗？+
单纯的前缀和不行——改一个元素会让它后面所有前缀和都失效，更新是 O(n)。这种「带修改」的区间和要用树状数组(BIT)或线段树，把更新和查询都做到 O(log n)。
二维版本怎么做？+
扩展成二维前缀和 pre[r][c]，子矩阵和用容斥：右下减去上、左两块再加回重复减掉的左上角，同样是 O(1) 查询。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 区域和检索 - 数组不可变 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。