BIT Implementation

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.