Segmen tree - minimum range query

MinimumRangeQuery.py

'''
  Segmentree:
  - construction: recursive like MergeSort, build leaves first then internal nodes 
  - Explanation: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
  - Basically:
  We need to construct a segmentree from an input array, then when query, there are three case than can be happened:
  + Case1: Range of current node is inside query range (full overlap)
  + Case2: Range of current node is completely outside query range (no overlap)
  + Case3: Range of current node is part of query range (partion overlap)
'''
class ArraySegmenTree:
    def __init__(self, arr):
        self._seg_tree = [float('Inf')]*(2*self._next_power_of_two(len(arr)) - 1)
        # input array
        self._arr = arr 
        self._construct_tree(self._arr, self._seg_tree, 0, len(self._arr)-1, 0)

    def _construct_tree(self, arr, seg_tree, low, high, count):
        if low >= high:
            # build two child first
            seg_tree[count] = (arr[low], (low, low))
            return
        mid = (low+high) // 2
        
        self._construct_tree(arr, seg_tree, low, mid, 2*count+1)
        self._construct_tree(arr, seg_tree, mid+1, high, 2*count+2)
        # then build the parent of two child above
        seg_tree[count] = (min(seg_tree[self._left(count)][0], seg_tree[self._right(count)][0]), (low, high))
    
    def query_min(self, qs, qe, pos):
        # since there are some 'Inf' elements
        # we need to check instance
        if isinstance(self._seg_tree[pos], float):
            return float('Inf')
        start, end = self._seg_tree[pos][1]
        min_val = self._seg_tree[pos][0]
        # print(start, end)
        # case1: range of node is within qs and qe 
        #       => return min value in node
        if qs <= start and qe >= end:
            return min_val
        # case2: range of node is outside qs and qe
        #       => return infinite
        if end < qs or start > qe:
            return float('Inf')
        # case3: range of node is partition overlapped with qs and qe 
        #       return min(query_min(node left child, qs qe), query_min(node right child, qs, qe))
        if self._has_child(pos):
            return min(self.query_min(qs, qe, self._left(pos)), self.query_min(qs, qe, self._right(pos)))
        else:
            return self._seg_tree[pos][0]
    def _is_power_of_two(self, n):
        return n > 0 and (n & (n-1)) == 0

    def _next_power_of_two(self, n):
        if self._is_power_of_two(n):
            return n
        count = 0
        while n > 0:
            count += 1
            n = n >> 1
        return 1 << count
    
    def _left(self, p):
        return p*2+1 
    
    def _right(self, p):
        return p*2+2

    def _has_child(self, p):
        return self._left(p) < len(self._seg_tree) and self._right(p) < len(self._seg_tree)

if __name__ == '__main__':
    from sys import stdin, stdout 
    n = int(stdin.readline())
    arr = [int(x) for x in stdin.readline().split()]
    seg_tree = ArraySegmenTree(arr)
    q = int(stdin.readline())
    for _ in range(q):
        qs, qe = [int(x) for x in stdin.readline().split()]
        print(seg_tree.query_min(qs, qe, 0))