http://www.lintcode.com/en/problem/segment-tree-build-ii/\#

因为需要记录下区间最小值，所以思路是先拆分，再从最小的区间计算出大区间。

public SegmentTreeNode build(int[] A) {
        // write your code here
        if (A == null || A.length == 0) {
            return null;
        }

        SegmentTreeNode root = buildHelper(A, 0, A.length - 1);
        return root;
    }


    public SegmentTreeNode buildHelper(int[] A, int start, int end) {
        if (start == end) {
            return new SegmentTreeNode(start, end, A[start]);
        }

        int mid = (start + end) / 2;

        SegmentTreeNode left = buildHelper(A, start, mid);
        SegmentTreeNode right = buildHelper(A, mid + 1, end);

        SegmentTreeNode root = new SegmentTreeNode(left.start, right.end, Math.max(left.max, right.max));
        root.left = left;
        root.right = right;

        return root;

    }