303. 区域和检索 - 数组不可变（Range Sum Query - Immutable）
频次 ★★★ · 难度 🟢 · 高频：全厂
题目
数组不可变，多次查询 sumRange(l, r)。
思路
一维前缀和：预处理 pre[i] = sum(nums[0..i-1])，sumRange(l, r) = pre[r+1] - pre[l]。
代码
class NumArray {
private 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 l, int r) {
return pre[r + 1] - pre[l];
}
}复杂度
- 时间：初始化 O(n)，查询 O(1)
- 空间：O(n)
边界条件
pre开n+1而不是n：pre[0] = 0表示空前缀。有了这个哨兵，sumRange(0, r)不需要单独判断左边界l == r：单元素，pre[r+1] - pre[l]自然退化为nums[l]- 空数组：
pre长度为 1，不会有合法查询打进来 - 整型溢出：本题数值范围小，但若元素是
int且 n 很大，pre应当用long
变式
- 304. 二维区域和检索：升到二维，容斥原理
- 560. 和为 K 的子数组：前缀和 + 哈希表，把「区间和等于 K」转成「查
pre[j] - K出现过几次」 - 数组可变（
update(i, val)）：前缀和失效，改用树状数组或线段树，把「查询 O(1)/更新 O(n)」换成「两者都 O(log n)」 - 前缀积：
238就是把加法换成乘法（但要处理 0，所以用左右两遍扫代替除法）
易错点
sumRange(l, r) = pre[r+1] - pre[l]，不是pre[r] - pre[l-1]。后者在l == 0时越界。哨兵存在的全部意义就是消灭这个特判- 前缀和数组的下标含义是「前 i 个元素之和」，比
nums的下标整体右移一位。写的时候心里要清楚pre[i]不包含nums[i] - 只在不可变数组上成立。一旦允许单点更新，
pre的后半段全部作废
面试追问
- 为什么这题的重点是”不可变”三个字：预处理换查询是有前提的——预处理结果必须能长期复用。数组一变，O(n) 的前缀和就要重算，摊到每次更新上就是 O(n)。所以题面里的 “Immutable” 不是废话，它是这个解法成立的授权。
- 区间和的三种数据结构怎么选：前缀和（查 O(1)、改 O(n)）、树状数组（都 O(log n)、代码短）、线段树（都 O(log n)、能维护任意可合并信息）。读多写少选前缀和，读写均衡选树状数组，需要区间修改或维护 max/min 之类选线段树。
- 这和数据库的物化视图是一回事吗：是。都是「用空间和更新成本，换查询成本」。物化视图在基表更新时要刷新，前缀和在数组更新时要重算，代价结构完全一致——这就是前缀和与差分这个套路的通用形态。
- 能不能只对热点区间预处理：能，这就是分块（把数组切成 √n 块，块内暴力、块间前缀和），查询和更新都是 O(√n)，是前缀和与暴力之间的折中。