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

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

动态求解，所以需要线段树来帮忙

build O(n)

query O(logn) 最多向下走logn次

modify o(logn) 最多遍历 logn * 2次

class SegmentTree {
    int start, end;
    long sum;
    SegmentTree left, right;
    public SegmentTree(int start, int end, long sum) {
        this.start = start;
        this.end = end;
        this.sum = sum;
    }
}
public class Solution {
    /* you may need to use some attributes here */

    /*
    * @param A: An integer array
    */
    SegmentTree root;
    public Solution(int[] A) {
        // do intialization if necessary
        root = build(A, 0, A.length - 1);
    }

    public SegmentTree build(int[] A, int start, int end) {
        if (A == null || A.length == 0) {
            return null;
        }

        if (start == end) {
            return new SegmentTree(start, end, (long) A[start]);
        }

        SegmentTree root = new SegmentTree(start, end, 0);

        int mid = (start + end) / 2;
        SegmentTree left = build(A, start, mid);
        SegmentTree right = build(A, mid + 1, end);

        root.left = left;
        root.right = right;
        root.sum = left.sum + right.sum;
        return root;

    }

    /*
     * @param start: An integer
     * @param end: An integer
     * @return: The sum from start to end
     */

    public long query(int start, int end) {
        return queryHelper(root, start, end);
    } 

    public long queryHelper(SegmentTree root, int start, int end) {
        // write your code here
        if (root == null) {
            return 0;
        }

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

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

        return queryHelper(root.left, start, mid) + queryHelper(root.right, mid + 1, end);
    }

    /*
     * @param index: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void modify(int index, int value) {
        // write your code here
        modifyHelper(root, index, value);
    }


    public void modifyHelper(SegmentTree root, int index, int value) {
        if (root == null) {
            return;
        }

        if (root.start == root.end) {
            if (root.start == index) {
                root.sum = value;
            }
            return;   
        }

        int mid = (root.start + root.end) / 2;
        if (index <= mid) {
            modifyHelper(root.left, index, value);
        } else {
            modifyHelper(root.right, index, value);
        }

        root.sum = root.left.sum + root.right.sum;
    }
}