class NumArray:
function init(nums):
this.n = nums.length
this.tree = array of 4*this.n zeros
if this.n > 0:
this.build(nums, 1, 0, this.n - 1)
function build(nums, node, start, end):
if start == end:
this.tree[node] = nums[start]
else:
mid = floor((start + end) / 2)
this.build(nums, 2*node, start, mid)
this.build(nums, 2*node+1, mid+1, end)
this.tree[node] = this.tree[2*node] + this.tree[2*node+1]
function update(index, val):
this.doUpdate(1, 0, this.n-1, index, val)
function sumRange(left, right):
return this.query(1, 0, this.n-1, left, right)
The public methods delegate to recursive helpers that track the current node's range.