Given an integer arraynums, find the sum of the elements between indicesiandj(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.

tag: segment tree

class NumArray {

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

        public SegmentTreeNode(int start, int end){
            this.start = start;
            this.end = end;
            left = null;
            right = null;
            sum = 0;
        }
    }

    SegmentTreeNode root = null;

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

    private SegmentTreeNode buildTree(int[] nums, int start, int end){
        if (start > end) return null;

        SegmentTreeNode ans = new SegmentTreeNode(start, end);
        if (start == end){
            ans.sum = nums[start];
        }
        else{
            int mid = start + (end - start) / 2;
            ans.left = buildTree(nums, start, mid);
            ans.right = buildTree(nums, mid + 1, end);
            ans.sum = ans.left.sum + ans.right.sum;
        }

        return ans;
    }

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

    private void update(SegmentTreeNode root, int pos, int val){
        if (root.start == root.end){
            root.sum = val;
            return;
        }

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

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

    private int sumRange(SegmentTreeNode root, int start, int end){
        if (root.start == start && root.end == end) return root.sum;

        int mid = root.start + (root.end - root.start) / 2;
        if (end <= mid) return sumRange(root.left, start, end);
        else if (start > mid) return sumRange(root.right, start, end);
        else return sumRange(root.left, start, mid) + sumRange(root.right, mid + 1, end);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */