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

https://leetcode-cn.com/problems/range-sum-query-immutable/

用前缀和数组，preSum[i]表示nums[0...i]的和，则求某个区间nums[i...j]的和就能转化为求preSum[j] - preSum[i-1] 细节：因为要计算preSum[i-1]，当i=0时下标溢出，因此令preSum[0]=0作辅助

class NumArray:

    def __init__(self, nums: List[int]):
        n=len(nums)
        self.preSum = [0] * (n+1)
        for i in range(n):
            self.preSum[i+1] = self.preSum[i] + nums[i]

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