Segment Tree Build II（線分樹の構造II）

http://www.lintcode.com/en/problem/segment-tree-build-ii/ Segment Tree Modify（線分樹の修正）を参照してください。最後にmaxの割り当てに注意してください。

/**
 * Definition of SegmentTreeNode:
 * public class SegmentTreeNode {
 * public int start, end, max;
 * public SegmentTreeNode left, right;
 * public SegmentTreeNode(int start, int end, int max) {
 * this.start = start;
 * this.end = end;
 * this.max = max
 * this.left = this.right = null;
 * }
 * }
 */


public class Solution {
    /*
     * @param A: a list of integer
     * @return: The root of Segment Tree
     */
    public SegmentTreeNode build(int[] A) {
        // write your code here
        return tree(A, 0, A.length - 1);
    }

    private SegmentTreeNode tree(int[] a, int start, int end) {
        if (start>end){
            return null;
        }
        SegmentTreeNode node = new SegmentTreeNode(start, end, a[start]);
        if (start == end) {
            return node;
        }
        int mid = (start + end) >>> 1;
        node.left = tree(a, start, mid);
        node.right = tree(a, mid + 1, end);
        
        node.max = Math.max(node.left.max, node.right.max);
        return node;
    }
}