303. Range Sum Query - Immutable

303. Range Sum Query - Immutable

class NumArray:

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

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

class BIT:
    def __init__(self, n: int):
        self.sums = [0] * (n + 1)

    def lowbit(self, i: int):
        return i & -i

    def update(self, i:int , delta: int):
        while i < len(self.sums):
            self.sums[i] += delta
            i += self.lowbit(i)

    def query(self, i: int) -> int:
        res = 0
        while i > 0:
            res += self.sums[i]
            i -= self.lowbit(i)
        return res

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        self.tree = BIT(len(nums))
        for i in range(len(self.nums)):
            self.tree.update(i + 1, nums[i])

    def sumRange(self, left: int, right: int) -> int:
        return self.tree.query(right + 1) - self.tree.query(left)


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