class NumArray:
def __init__(self, nums):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
if self.n > 0:
self._build(nums, 1, 0, self.n - 1)
def _build(self, nums, node, start, end):
if start == end:
self.tree[node] = nums[start]
else:
mid = (start + end) // 2
self._build(nums, 2*node, start, mid)
self._build(nums, 2*node+1, mid+1, end)
self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
def update(self, index, val):
self._update(1, 0, self.n-1, index, val)
def sumRange(self, left, right):
return self._query(1, 0, self.n-1, left, right)
The public methods delegate to recursive helpers that track the current node's range.