LeetCode - Range Sum Query - Mutable

Question Definition

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

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

1. The array is only modifiable by the update function.
2. You may assume the number of calls to update and sumRange function is distributed evenly.

   Java Solution

   class NumArray {
    private TreeNode root;
    private int[] nums;
    public NumArray(int[] nums) {
        if(nums.length == 0) return;
        root = new TreeNode(nums, 0, nums.length);
        this.nums = nums;
    }
   
    public void update(int i, int val) {
        int change = val - nums[i];
        nums[i] = val;
        TreeNode cur = root;
        while(cur != null){
            cur.sum += change;
            if(cur.left != null && i >= cur.left.range[0] && i < cur.left.range[1]){
                cur = cur.left;
            } else if(cur.right != null && i >= cur.right.range[0] && i < cur.right.range[1]){
                cur = cur.right;
            } else
                break;
        }
    }
   
    public int sumRange(int i, int j) {
        return sumRange(root, i, j + 1);
    }
   
    private int sumRange(TreeNode cur, int i, int j){
        if(cur == null || i < cur.range[0] || j > cur.range[1])
            return -1;
        if(cur.range[0] == i && cur.range[1] == j)
            return cur.sum;
        int mid = (cur.range[0] + cur.range[1]) / 2;
        if(j <= mid)
            return sumRange(cur.left, i, j);
        if(i >= mid)
            return sumRange(cur.right, i, j);
        return sumRange(cur.left, i, mid) + sumRange(cur.right, mid, j);
    }
   
    class TreeNode {
        int[] range;
        int sum;
        TreeNode left;
        TreeNode right;
   
        TreeNode(int[] nums, int start, int end){
            this.range = new int[]{start, end};
            int mid = (start + end) / 2;
            if(start < end - 1){
                left = new TreeNode(nums, start, mid);
                right = new TreeNode(nums, mid, end);
                this.sum = left.sum + right.sum;
            }else {
                this.sum = nums[start];
            }
        }
    }
   }