303. 区域和检索 - 数组不可变

题目链接：303. 区域和检索 - 数组不可变

题目描述

给定一个整数数组 nums，处理以下类型的多个查询：计算索引 left 和 right（包含 left 和 right）之间的 nums 元素的和，其中 left <= right。

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象。
• int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的元素的总和。

核心思考：前缀和

这道题的本质就是前缀和（Prefix Sum）。

如果每次调用 sumRange 都遍历区间 [left, right] 来累加求和，单次查询的时间复杂度为 $O(N)$。当查询次数很多时，这种做法效率很差。

前缀和的思路是：在初始化阶段预先计算好一个前缀和数组 s，其中 s[i] 表示原数组前 i 个元素的总和。这样，任何区间 [left, right] 的和都可以通过一次减法得到：

$$sumRange(left, right) = s[right + 1] - s[left]$$

这里 s 的长度比 nums 多 1，s[0] = 0 作为边界条件，避免了对 left = 0 的特殊处理。

解题思路 (Python)

class NumArray:

    def __init__(self, nums: List[int]):
        s = [0] * (len(nums) + 1)
        for i,x in enumerate(nums):
            s[i + 1] = s[i] + x
        self.s = s

    def sumRange(self, left: int, right: int) -> int:
        return self.s[right + 1] - self.s[left]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

复杂度分析

• 时间复杂度：
  • 初始化：$O(N)$，其中 $N$ 是数组 nums 的长度。需要遍历一次数组来构建前缀和。
  • 单次查询：$O(1)$。每次调用 sumRange 只需要做一次减法运算。
• 空间复杂度：$O(N)$。需要额外存储一个长度为 $N + 1$ 的前缀和数组。