class NumArray:
def __init__(self, nums):
self.n = len(nums)
self.nums = nums[:]
self.tree = [0] * (self.n + 1)
for i, x in enumerate(nums):
self._add(i + 1, x)
def _add(self, i, delta):
while i <= self.n:
self.tree[i] += delta
i += i & (-i)
def _prefix(self, i):
result = 0
while i > 0:
result += self.tree[i]
i -= i & (-i)
return result
def update(self, index, val):
delta = val - self.nums[index]
self.nums[index] = val
self._add(index + 1, delta)
def sumRange(self, left, right):
return self._prefix(right + 1) - self._prefix(left)
Note: we keep a copy of nums to compute deltas for updates.