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.

interval_minimum_number.py

class SegmentTreeNode:
    def __init__(self, st, ed, mval):
        self.st = st
        self.ed = ed
        self.min = mval

class SegmentTree:
    def __init__(self, arr):
        if not arr:
            raise 'Empty input array'
        self.root = self.build(arr, 0, len(arr) - 1)

    def build(self, arr, st, ed):
        if st == ed:
            return SegmentTreeNode(st, ed, arr[st])

        mid = (st + ed) / 2
        root = SegmentTreeNode(st, ed, -1)
        root.left = self.build(arr, st, mid)
        root.right = self.build(arr, mid + 1, ed)
        root.min = min(root.left.min, root.right.min)
        return root

    def query(self, st, ed):
        if st > ed:
            return
        return self.helper(self.root, max(st, self.root.st), min(ed, self.root.ed))

    def helper(self, root, st, ed):
        if root.st == st and root.ed == ed:
            return root.min

        mid = (root.st + root.ed) / 2
        left = right = 2**31 - 1
        if st <= mid:
            left = self.helper(root.left, st, min(mid, ed))
        if mid + 1 <= ed:
            right = self.helper(root.right, max(mid + 1, st), ed)
        return min(left, right)


class Solution:
    """
    @param A, queries: Given an integer array and an Interval list
                       The ith query is [queries[i-1].start, queries[i-1].end]
    @return: The result list
    """
    def intervalMinNumber(self, A, queries):
        if not A:
            return []

        st = SegmentTree(A)
        ret = []
        for start, end in queries:
            ret.append(st.query(start, end))
        return ret

if __name__ == '__main__':
    s = Solution()
    print(s.intervalMinNumber([1,2,7,8,5], [(1,2), (0,4)]))