区域和检索 – 数组不可变 | LeetCode 303
内容提要
LeetCode 303 要求实现 NumArray 类，以支持多次查询数组任意区间 [left, right] 的元素和。解法采用前缀和：初始化时构建 preSum 数组记录累加和，查询时用 preSum[right+1] 减去 preSum[left] 得到结果。初始化时间复杂度 O(n)，每次查询 O(1)，空间复杂度 O(n)。
延伸解读
前缀和数组的设计细节
文章使用长度为 n+1 的 preSum 数组，其中 preSum[i] 表示 nums[0..i-1] 的累加和。这样设计的好处是查询区间 [left, right] 时直接计算 preSum[right+1] - preSum[left]，无需对 left 是否为 0 做特殊处理，边界更统一。初始化时从下标 1 开始填充 preSum，保证 preSum[0] 为 0，作为空区间和的基准。
查询效率与适用场景
由于每次 sumRange 只涉及两次数组访问和一次减法，时间复杂度为 O(1)，非常适合查询次数远多于修改的场景。题目中 sumRange 最多调用 10^4 次，前缀和方案能有效避免每次查询都遍历区间。但该方案假设数组不可变，若元素需要频繁更新，前缀和数组需重新构建，反而可能不如其他数据结构灵活。
复杂度与实现权衡
初始化需遍历一次数组构建前缀和，时间复杂度 O(n)，空间复杂度 O(n) 用于存储 preSum。相比每次查询直接累加（单次 O(k)，k 为区间长度），前缀和以一次性 O(n) 的预处理换取后续查询的常数时间。在查询次数较多时优势明显，但若查询很少或数组极大，额外空间和初始化开销也需要纳入考虑。
Q&A
LeetCode 303 要求实现什么类，它需要支持什么操作？
要求实现 NumArray 类，支持用整数数组 nums 初始化对象，并实现 sumRange(left, right) 方法，返回 nums 在索引 left 和 right 之间（包含两端）的元素总和。
为什么用前缀和数组可以快速计算区间和？
因为前缀和数组 preSum 记录了从开头到每个位置的累加和，区间 [left, right] 的和等于 preSum[right+1] - preSum[left]，只需一次减法即可得到结果。
NumArray 类的初始化过程是怎样的？
初始化时创建一个长度为 n+1 的 preSum 数组，其中 preSum[i] 表示 nums[0..i-1] 的累加和，通过遍历 nums 一次构建完成。
sumRange 方法的时间复杂度是多少？
每次调用 sumRange 的时间复杂度是 O(1)，因为只需要用 preSum[right+1] 减去 preSum[left] 得到结果。
这个解法整体的时间和空间复杂度如何？
初始化时间复杂度 O(n)，每次查询 O(1)，空间复杂度 O(n)，需要额外创建一个长度为 n+1 的前缀和数组。
sumRange 方法中 left 和 right 参数的含义是什么？
left 和 right 是数组 nums 的索引，表示要计算和的区间起点和终点，包含 left 和 right 两个端点，且满足 left <= right。
