http://www.lintcode.com/en/problem/interval-minimum-number/

nothing much to say. for a range what's the minimum value. build the tree from ground up

/**
 * Definition of Interval:
 * public classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 */
public class Solution {
    /**
     *@param A, queries: Given an integer array and an query list
     *@return: The result list
     */
    class SegmentTreeNode {
        int start;
        int end;
        int min;
        SegmentTreeNode left;
        SegmentTreeNode right;

        public SegmentTreeNode(int start, int end, int min) {
            this.start = start;
            this.end = end;
            this.min = min;
            this.left = null;
            this.right = null;
        }
    }

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

        int mid = (start + end) / 2;

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

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

        return root;
    }

    public int search(SegmentTreeNode root, Interval interval) {
        if (interval.start == root.start && interval.end == root.end) {
            return root.min;
        }

        int mid = (root.start + root.end) / 2;

        if (interval.start > mid) {
            return search(root.right, interval);
        } else if (interval.end <= mid) {
            return search(root.left, interval);
        }

        int left = search(root.left, new Interval(interval.start, mid));
        int right = search(root.right, new Interval(mid + 1, interval.end));

        return Math.min(left, right);
    }
    public ArrayList<Integer> intervalMinNumber(int[] A, 
                                                ArrayList<Interval> queries) {
        // write your code here
        ArrayList<Integer> ans = new ArrayList<Integer>();
        if (A == null) {
            return ans;
        }

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

        for (int i = 0; i < queries.size(); i++) {
            ans.add(search(root, queries.get(i)));
        }

        return ans;
    }
}