[LintCode] Interval Minimum Number

Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers[start, end]. For each query, calculate the minimum number between index start and end in the given array, return the result list.

Example

For array [1,2,7,8,5], and queries [(1,2),(0,4),(2,4)], return [2,1,5]

Segment Tree:

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 */
class Solution { 
public:
    /**
     *@param A, queries: Given an integer array and an query list
     *@return: The result list
     */
    int query(SegmentTreeNode *root, int start, int end)
    {
        if(root->start == start && root->end == end) return root->max;
        int mid = (root->start+root->end)/2;
        if(end <= mid) return query(root->left, start, end);
        if(start > mid) return query(root->right, start, end);
        if(mid < end) return min(query(root->left, start, mid), query(root->right, mid+1, end));
    }
    SegmentTreeNode *build(vector<int>&A, int start, int end)
    {
        if(start>end) return NULL;
        if(start == end) return new SegmentTreeNode(start, start, A[start]);
        int mid = (start+end)/2;
        SegmentTreeNode *left = build(A, start, mid);
        SegmentTreeNode *right = build(A, mid+1, end);
        SegmentTreeNode *node = new SegmentTreeNode(start, end, min(left->max, right->max));
    
        node->left = left;
        node->right = right;
        return node;
    }
    
    vector<int> intervalMinNumber(vector<int> &A, vector<Interval> &queries) {
        // write your code here
        vector<int> res;
    
        SegmentTreeNode *root = build(A, 0, A.size()-1);
        if(!root) return res;
        
        for(auto e:queries)
        {
            res.push_back(query(root,e.start, e.end));
        }
        return res;
    }
};