Segment Tree Implementation

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.