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

divide and conquer from bottom up

public SegmentTreeNode build(int start, int end) {
        if (start > end) {
            return null;
        }
        if (start == end) {
            return new SegmentTreeNode(start, end);
        }

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

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

        return root;

    }