SegmentTree in Python

SegmentTree.py

INF = 999999999999999

class SegTreeNode(object):
    def __init__(self, left, right, data):
        self.left = left
        self.right = right
        self.data = data
        self.left_child = None
        self.right_child = None
    
    def __repr__(self):
        return "<node left:%d right:%d data:%d>" % (self.left, self.right, self.data)

class SegTree(object):
    def __init__(self, left, right):
        self.root = self.make_tree(left, right)

    def make_tree(self, left, right):
        node = SegTreeNode(left, right, INF)
        if left < right:
            mid = (left + right) / 2
            node.left_child = self.make_tree(left, mid)
            node.right_child = self.make_tree(mid + 1, right)
        return node

    def _update(self, left, right, val, node):
        if right < node.left or left > node.right:
            return
        if node.left_child and left <= node.left_child.right:
            self._update(left, right, val, node.left_child)
        if node.right_child and right >= node.right_child.left:
            self._update(left, right, val, node.right_child)
        if node.left >= left and node.right <= right:
            node.data = min(node.data, val)
    
    def update(self, left, right, val):
        self._update(left, right, val, self.root)
    
    def _query(self, left, right, node):
        if node is None or right < node.left or left > node.right:
            return INF
        if node.left >= left and node.right <= right:
            return node.data
        return min(self._query(left, right, node.left_child), self._query(left, right, node.right_child))

    def query(self, left, right):
        return self._query(left, right, self.root)