Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

• Time: O(n)
• Space: O(n)

public class NumArray {

    class SegmentTreeNode {
        int start, end;
        SegmentTreeNode left, right;
        int sum;

        public SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    SegmentTreeNode root = null;

    public NumArray(int[] nums) {
        if (nums.length > 0) {
            root = build(nums, 0, nums.length - 1);
        }
    }

    private SegmentTreeNode build(int[] nums, int start, int end) {
        SegmentTreeNode ret = new SegmentTreeNode(start, end);
        if (start == end) {
            ret.sum = nums[start];
        } else {
            int mid = (start + end) / 2;
            ret.left = build(nums, start, mid);
            ret.right = build(nums, mid + 1, end);
            ret.sum = ret.left.sum + ret.right.sum;
        }
        return ret;
    }

    void update(int i, int val) {
        update(root, i, val);
    }

    void update(SegmentTreeNode node, int pos, int val) {
        if (node.start == node.end) {
            node.sum = val;
        } else {
            int mid = (node.start + node.end) / 2;
            if (pos <= mid) {
                update(node.left, pos, val);
            } else {
                update(node.right, pos, val);
            }
            node.sum = node.left.sum + node.right.sum;
        }
    }

    public int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }

    public int sumRange(SegmentTreeNode node, int start, int end) {
        if (node.end == end && node.start == start) {
            return node.sum;
        } else {
            int mid = (node.start + node.end) / 2;
            if (end <= mid) {
                return sumRange(node.left, start, end);
            } else if (start > mid) {
                return sumRange(node.right, start, end);
            } else {
                return sumRange(node.left, start, mid) + 
                       sumRange(node.right, mid + 1, end);
            }
        }
    }
}