Interval Sum II

Interval Sum II

24%

Accepted

Given an integer array in the construct method, implement two methods query(start, end) andmodify(index, value):

• For query(start, end), return the sum from index startto index end in the given array.
• For modify(index, value), modify the number in the given index to value

Have you met this question in a real interview? 

Yes

Example

Given array A = [1,2,7,8,5].

• query(0, 2), return 10.
• modify(0, 4), change A[0] from 1 to 4.
• query(0, 1), return 6.
• modify(2, 1), change A[2] from 7 to 1.
• query(2, 4), return 14.

Note

We suggest you finish problem Segment Tree Build, Segment Tree Query andSegment Tree Modify first.

Challenge

O(logN) time for query and modify.

public class Solution {

    /* you may need to use some attributes here */

    

    /**

     * @param A: An integer array

     */

     SumTreeNode root;

    public Solution(int[] A) {

        // write your code here

        root = buildingTree(A, 0, A.length-1);

    }

    

    /**

     * @param start, end: Indices

     * @return: The sum from start to end

     */

    public long query(int start, int end) {

        // write your code here

        return querySum(root, start, end);

    }

    

    /**

     * @param index, value: modify A[index] to value.

     */

    public void modify(int index, int value) {

        // write your code here

        subModify(root, index, value);

    }

    

    private long querySum(SumTreeNode root, int start, int end){

        if(root == null || root.start > end || root.end < start ) return 0;

        if(root.start >= start && root.end <= end) return root.sum;

        return querySum(root.left, start, end) + querySum(root.right, start, end);

    }

    

    private void subModify(SumTreeNode root, int index, int value){

        if(root == null || root.start > index || root.end < index) return;

        if(root.start == root.end){

            root.sum = value;

            return;

        }

        if((root.start + root.end) / 2 >= index){

            subModify(root.left, index, value);

        }else{

            subModify(root.right, index, value);

        }

        long sum = root.left == null ? 0 : root.left.sum;

        sum += root.right == null ? 0 : root.right.sum;

        root.sum = sum;

        

    }

    private SumTreeNode buildingTree(int[] A, int start, int end){

        if(A == null || start > end){

            return null;

        }

        if(start == end){

            return new SumTreeNode((long)A[start], start, end);

        }

        SumTreeNode root = new SumTreeNode(start, end);

        root.left = buildingTree(A, start, (start + end) / 2);

        root.right = buildingTree(A, (start + end) / 2 + 1, end);

        root.sum = root.left == null ? 0 : root.left.sum;

        root.sum += root.right == null ? 0 : root.right.sum;

        

        return root;

        

    }

    

    class SumTreeNode{

        long sum;

        int start;

        int end;

        SumTreeNode left;

        SumTreeNode right;

        

        public SumTreeNode(int start, int end){

            this.start = start;

            this.end = end;

            

        }

        public SumTreeNode(long sum, int start, int end){

            this.start = start;

            this.end = end;

            this.sum = sum;

        }

    }

}