🔗 题目信息
💡 核心思路
题目要求多次查询数组在范围 $[left, right]$ 内的元素总和。若暴力遍历，单次查询复杂度为 $O(n)$，在 $m$ 次查询下总复杂度 $O(mn)$ 会超时。
利用**前缀和（Prefix Sum）**思想：
- 预处理：构建辅助数组 $s$，其中 $s[i]$ 存储原数组前 $i$ 个元素的累加和。
- 偏移对齐：为了处理边界，令 $s[0] = 0$，则 $s[i] = \sum_{j=0}^{i-1} nums[j]$。
- 区间计算：查询 $[left, right]$ 的闭区间和，公式为：
$$Sum(left, right) = s[right+1] - s[left]$$
🐍 Python 工程实现
在 Python 环境中，利用 itertools.accumulate 构造前缀和是最符合工程直觉且性能优秀的方式。使用 uv 运行此脚本可确保环境纯净。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
from itertools import accumulate
from typing import List
class NumArray:
def __init__(self, nums: List[int]):
"""
使用 itertools.accumulate 快速预处理
self.s[i] 表示 nums[0...i-1] 的元素之和
"""
# 严谨处理：增加首位 0 以应对 left=0 的边界情况
# 此时 len(self.s) == len(nums) + 1
self.s = [0] + list(accumulate(nums))
def sumRange(self, left: int, right: int) -> int:
"""
O(1) 复杂度查询区间和
"""
# 由于 self.s 补了 0，原数组下标 k 对应 s[k+1]
# [left, right] 的和即为 s[right+1] - s[left]
return self.s[right + 1] - self.s[left]
|