307. Range Sum Query - Mutable

/*
Using Segment Tree

Time Complexity:
1. NumArray = O(N)
2. update = O(log N)
3. sumRange = O(log N)

Space Complexity: O(N)
*/
class NumArray {

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

        SegmentTreeNode (int s, int e) {
            start = s;
            end = e;
        }
    }

    SegmentTreeNode root;

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

    private SegmentTreeNode buildTree(int[] nums, int s, int e) {
        if (s > e) {
            return null;
        }
        SegmentTreeNode node = new SegmentTreeNode(s, e);
        if (s == e) {
            node.sum = nums[s];
        } else {
            int mid = s + (e-s)/2;
            node.left = buildTree(nums, s, mid);
            node.right = buildTree(nums, mid+1, e);
            node.sum = node.left.sum + node.right.sum;
        }
        return node;
    }

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

    private void updateTree(SegmentTreeNode node, int i, int val) {
        if (node.start == node.end && node.start == i) {
            node.sum = val;
            return;
        }
        int mid = node.start + (node.end - node.start)/2;
        if (i <= mid) {
            updateTree(node.left, i, val);
        } else {
            updateTree(node.right, i, val);
        }
        node.sum = node.left.sum + node.right.sum;
    }

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

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


/*
Using Binary Indexed Tree
Refer:
1) https://leetcode.com/problems/range-sum-query-mutable/discuss/75753/Java-using-Binary-Indexed-Tree-with-clear-explanation
2) https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/

Time Complexity:
1. NumArray = O(N logN)
2. update = O(log N)
3. sumRange = O(log N)

Space Complexity: O(N)
*/
class NumArray {
    int[] numArr;
    int[] tree;
    int maxIdx;

    public NumArray(int[] nums) throws IllegalArgumentException {
        if (nums == null) {
            throw new IllegalArgumentException("Input nums array is null");
        }
        numArr = nums;
        int len = numArr.length;
        tree = new int[len+1];
        maxIdx = len;

        for (int i = 0; i < len; i++) {
            updateHelper(i+1, numArr[i]);
        }
    }

    public void update(int i, int val) {
        int diff = val - numArr[i];
        numArr[i] = val;
        updateHelper(i+1, diff);
    }

    private void updateHelper(int i, int diff) {
        while (i <= maxIdx) {
            tree[i] += diff;
            i += i & -i;
        }
    }

    public int sumRange(int i, int j) {
        return readIdx(j+1) - readIdx(i);
    }

    private int readIdx(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx &= idx-1;
        }
        return sum;
    }
}


/*
Using Binary Indexed Tree with optimization.
It uses cumulative sum array for initializing the tree;
Refer:
1) https://leetcode.com/problems/range-sum-query-mutable/discuss/75753/Java-using-Binary-Indexed-Tree-with-clear-explanation/166940
2) https://www.topcoder.com/community/competitive-programming/tutorials/binary-indexed-trees/

Time Complexity:
1. NumArray = O(N)
2. update = O(log N)
3. sumRange = O(log N)

Space Complexity: O(N)
*/
class NumArray {
    int[] numArr;
    int[] tree;
    int maxIdx;

    public NumArray(int[] nums) throws IllegalArgumentException {
        if (nums == null) {
            throw new IllegalArgumentException("Input nums array is null");
        }

        numArr = nums;
        maxIdx = nums.length;

        int[] csArr = new int[maxIdx+1];
        for (int i = 0; i < maxIdx; i++) {
            csArr[i+1] = csArr[i] + nums[i];
        }

        tree = new int[maxIdx+1];

        for (int i = 1; i <= maxIdx; i++) {
            tree[i] = csArr[i] - csArr[i - (i & -i)];
        }
    }

    public void update(int i, int val) {
        int diff = val - numArr[i];
        numArr[i] = val;
        i++;
        while (i <= maxIdx) {
            tree[i] += diff;
            i += i & -i;
        }
    }

    public int sumRange(int i, int j) {
        return readIdx(j+1) - readIdx(i);
    }

    private int readIdx(int idx) {
        int sum = 0;
        while (idx > 0) {
            sum += tree[idx];
            idx &= idx-1;
        }
        return sum;
    }
}

/**
 * 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);
 */