0303. Range Sum Query - Immutable¶
题目信息¶
- 题号:
0303
- 难度:
Easy
- 主题:
数组、区间和、只读对象、多次查询
- 原题:
- 重点:
查询区间包含两个端点、构造后数组不再更新、多次调用共享同一对象状态
题目重述¶
实现 NumArray 类。构造函数接收整数数组 nums 并保存其只读数据;之后可以多次调用 sumRange(left, right),返回下标从 left 到 right 的所有元素之和,两个端点都包含在内。
nums 的长度位于 [1, 10^4],每个元素位于 [-10^5, 10^5]。每次查询都满足 0 <= left <= right < nums.length,调用 sumRange 的次数不超过 10^4。各次查询基于构造时的同一数组,题目不提供更新操作。
自建示例¶
连续进行不同范围的查询:
输入:NumArray([4, -2, 7, 1])
sumRange(0, 1)
sumRange(1, 3)
输出:2
6
解释:第一个闭区间包含 4 和 -2;第二个闭区间包含 -2、7 和 1。两次查询都读取构造时的原数组。
单元素区间:
输入:NumArray([-6, 3, 8]),sumRange(1, 1)
输出:3
解释:左右端点相同,区间只包含下标 1 的一个元素。
前缀和把闭区间变成两个边界¶
数组构造完成后不会再变化,因此没有必要为每一次查询重新累加。定义 prefix[i] 为前 i 个元素的和,也就是原数组下标 0 到 i-1 的元素之和;prefix[0] 是空前缀,值为零。
对闭区间 [left, right],prefix[right + 1] 包含了右端点,而 prefix[left] 恰好包含左端点之前的所有元素。两者相减后,留下的正是 left 到 right。使用 right + 1 是处理闭区间边界的关键,单元素区间也自然成立。
C++ 实现¶
class NumArray {
std::vector<long long> prefix;
public:
NumArray(std::vector<int>& nums)
: prefix(nums.size() + 1, 0) {
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
prefix[i + 1] = prefix[i] + nums[i];
}
}
int sumRange(int left, int right) {
return static_cast<int>(prefix[right + 1] - prefix[left]);
}
};
代码分析¶
前缀数组只在构造时建立一次;查询不读取或修改原数组,只通过两个前缀边界相减得到答案。内部使用 long long 保存累加值,避免把“若干整数相加”的中间结果过早限制在单个元素的类型中。构造时间为 O(n),每次查询为 O(1),额外空间为 O(n)。