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