class NumArray:
function init(nums):
this.n = nums.length
this.nums = copy(nums)
this.tree = array of size (this.n + 1), filled with 0
for i = 0 to nums.length - 1:
this._add(i + 1, nums[i])
function _add(i, delta):
while i <= this.n:
this.tree[i] += delta
i += i & (-i)
function _prefix(i):
result = 0
while i > 0:
result += this.tree[i]
i -= i & (-i)
return result
function update(index, val):
delta = val - this.nums[index]
this.nums[index] = val
this._add(index + 1, delta)
function sumRange(left, right):
return this._prefix(right + 1) - this._prefix(left)
Note: we keep a copy of nums to compute deltas for updates.