Interval Minimum Number

Question

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]

Thoughts

线段树问题，注意build的时候就可以将value设好

Solution

"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""


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):
        # write your code here
        segT = SegmentTree()
        length = len(A)
        root = segT.build(0, length-1, A)
        res = []
        for q in queries:
            ans = segT.query(root, q.start, q.end)
            res.append(ans)
        return res


class SegmentTree:

    def __init__(self):
        self.root = None

    def build(self, start, end, A):
        if start > end:
            return None
        root = SegmentTreeNode(start, end, 0)

        if start < end:
            mid = (start + end) / 2
            root.left = self.build(start, mid, A)
            root.right = self.build(mid+1, end, A)
            root.count = min(root.left.count, root.right.count)
        else:
            root.count = A[start]

        return root

    def query(self, root, start, end):
        if not root:
            return sys.maxint
        rStart = root.start
        rEnd = root.end

        if (rStart > end) or ( rEnd < start):
            return sys.maxint

        #should be >= and <=
        #if query range if larger than the segment tree range, just return the count
        if rStart >= start and rEnd <= end:
            return root.count

        leftCount = sys.maxint
        rightCount = sys.maxint

        mid = (rStart + rEnd) / 2
        if start <= mid:
            if end > mid:
                #some range are in right part
                leftCount = self.query(root.left, start, mid)
            else:
                leftCount = self.query(root.left, start, end)
        if mid < end:
            if start <= mid:
                #some range are in left part
                #right part should start with mid + 1
                rightCount = self.query(root.right, mid + 1, end)
            else:
                rightCount = self.query(root.right, start, end)
        return min(leftCount, rightCount)

    def modify(self, root, index, value):
        if root.start == index and root.end == index:
            root.count += value
            return

        mid = (root.start + root.end) / 2
        if root.start <= index and index <= mid:
            self.modify(root.left, index, value)
        elif root.end >= index and index > mid:
            self.modify(root.right, index, value)

        root.count = root.left.count + root.right.coun