303. 区域和检索 - 数组不可变
题目描述
输入一个整数数组 nums，之后会有很多次查询。每次查询给出两个下标 left 和 right（left <= right，下标从 0 开始），要求算出这一段元素的和。
实现 NumArray 类。构造函数接收数组 nums 并完成预处理。方法 sumRange(left, right) 返回从 nums[left] 一直加到 nums[right] 的结果，两端都计入。
数组在初始化后不会被修改。输入由方法名数组和参数数组组成，输出按顺序给出每次调用的返回值，构造调用记为 null。
示例 1
输入：操作 = ["NumArray","sumRange","sumRange","sumRange"] 参数 = [[[-2,0,3,-5,2,-1]],[0,2],[2,5],[0,5]] 输出：[null,1,-1,-3]
解释：三次查询分别是 (-2) + 0 + 3 = 1、3 + (-5) + 2 + (-1) = -1、全部元素之和 -3。
数据范围
1 <= nums.length <= 10^4-10^5 <= nums[i] <= 10^50 <= left <= right < nums.lengthsumRange最多调用10^4次。
解题思路
构造时预处理前缀和 pre，pre[i] 是前 i 个元素的和（pre[0] = 0）。区间 [left, right] 的和就是 pre[right+1] - pre[left]，每次查询只做一次减法。
为什么正确
pre[i] = nums[0] + nums[1] + ... + nums[i-1]。
复杂度分析
构造 O(n)，每次查询 O(1)；空间 O(n)。
易错点
前缀和数组比 nums 长 1，右端用 pre[right+1]；写成 pre[right] - pre[left] 会漏掉 nums[right]。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class NumArray:
def __init__(self, nums: List[int]):
self.pre = [0]
for x in nums:
self.pre.append(self.pre[-1] + x)
def sumRange(self, left: int, right: int) -> int:
return self.pre[right + 1] - self.pre[left]class NumArray {
private final int[] pre;
public NumArray(int[] nums) {
pre = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++)
pre[i + 1] = pre[i] + nums[i];
}
public int sumRange(int left, int right) {
return pre[right + 1] - pre[left];
}
}class NumArray {
vector<int> pre{0};
public:
NumArray(vector<int>& nums) {
for (int x : nums)
pre.push_back(pre.back() + x);
}
int sumRange(int left, int right) {
return pre[right + 1] - pre[left];
}
};type NumArray struct {
pre []int
}
func Constructor(nums []int) NumArray {
pre := []int{0}
for _, x := range nums {
pre = append(pre, pre[len(pre)-1]+x)
}
return NumArray{pre}
}
func (this *NumArray) SumRange(left int, right int) int {
return this.pre[right+1] - this.pre[left]
}var NumArray = function(nums) {
this.pre = [0];
for (const x of nums)
this.pre.push(this.pre[this.pre.length - 1] + x);
};
NumArray.prototype.sumRange = function(left, right) {
return this.pre[right + 1] - this.pre[left];
};class NumArray {
private pre: number[] = [0];
constructor(nums: number[]) {
for (const x of nums)
this.pre.push(this.pre[this.pre.length - 1] + x);
}
sumRange(left: number, right: number): number {
return this.pre[right + 1] - this.pre[left];
}
}