'''
keys: 
Solutions:
Similar:
T:
S:
'''
from typing import List

# caching, pre-compute the cummulative sum from index 0 to k
# sum_: sum of index 0 to index k-1
# T: O(1) per query, O(n) for pre-computation
# S: O(n)
class NumArray3:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.sum_ = [0] * (len(nums)+1)
        for i in range(len(nums)):
            self.sum_[i+1] = self.sum_[i] + nums[i]

    def sumRange(self, i: int, j: int) -> int:
        return self.sum_[j+1] - self.sum_[i]
        
        

import collections
# caching, e.g., sumRange is called many times with the same arguments
# TLE, T: O(1) and S: O(n^2)
class NumArray1:
    def __init__(self, nums: List[int]):
        self.nums = nums
        self.hash_map = collections.defaultdict(int)
        for i in range(len(nums)):
            sum_ = 0
            for j in range(i, len(nums)):
                sum_ += nums[j]
                self.hash_map[(i,j)] = sum_

    def sumRange(self, i: int, j: int) -> int:
        return self.hash_map[(i, j)]
    
# brutal force, or using loop and add
# T: O(n) for each query, S: O(1)
class NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums

    def sumRange(self, i: int, j: int) -> int:
        return sum(self.nums[i, j+1])
        


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