I've implemented a Segment Tree in Python3:import mathINF = int(2e9)class SegmentTreeNode:    def __init__(self, l, r, v=INF):        self.left = l        self.right = r        self.value = v    def merge(self, left, right):        if left is not None and right is not None:            self.value = min(left.value, right.value)        elif left is None and right is None:            self.value = INF        elif left is None:            self.value = right.value        else:            self.value = left.valueclass SegmentTree:    def __init__(self, a):        n = len(a)        power = math.ceil(math.log(n, 2))        total = 2 ** (power + 1)        self.__tree = [None] * int(total)        self.__leaf_length = int(total/2)-1        self.__build(1, 0, self.__leaf_length, a)    def __build(self, node, l, r, a):        if l == r:            self.__tree[node] = SegmentTreeNode(l, r)            try:                self.__tree[node].value = a[l]            except IndexError:                self.__tree[node].value = INF            return        leftchild = 2 * node        rightchild = leftchild + 1        mid = (l + r) // 2        self.__build(leftchild, l, mid, a)        self.__build(rightchild, mid + 1, r, a)        self.__tree[node] = SegmentTreeNode(l, r)        l = self.__tree[leftchild]        r = self.__tree[rightchild]        self.__tree[node].merge(l, r)    def __query(self, node, l, r, i, j):        if l >= i and r <= j:            return self.__tree[node]        elif j < l or i > r:            return None        else:            leftchild = 2 * node            rightchild = leftchild + 1            mid = (l + r) // 2            l = self.__query(leftchild, l, mid, i, j)            r = self.__query(rightchild, mid + 1, r, i, j)            if l is not None and r is not None:                return SegmentTreeNode(-1, -1, min(l.value, r.value))            elif l is None and r is None:                return SegmentTreeNode(-1, -1, INF)            elif l is None:                return SegmentTreeNode(-1, -1, r.value)            else:                return SegmentTreeNode(-1, -1, l.value)    def query(self, i, j):         return self.__query(1, 0, self.__leaf_length, i, j)    def __update(self, node, l, r, i, v):        if l == i and r == i:            self.__tree[node].value = v        elif i < l or i > r:            return None        else:            leftchild = 2 * node            rightchild = leftchild + 1            mid = (l + r) // 2            self.__update(leftchild, l, mid, i, v)            self.__update(rightchild, mid + 1, r, i, v)            l = self.__tree[leftchild]            r = self.__tree[rightchild]            self.__tree[node].merge(l, r)    def update(self, i, value):        self.__update(1, 0, self.__leaf_length, i, value)in_n, in_m = map(int, input().rsplit())in_array = list(map(int, input().rsplit()))segment_tree = SegmentTree(in_array)for row in range(in_m):    command = input().rsplit()    x, y = map(int, command[1:])    if command[0] == 'Min':        print(segment_tree.query(x - 1, y - 1).value)    else:        segment_tree.update(x-1, y)I take n and m from stdin after I read an array[n]. And then I read m operations Set I X or Min L R.Here is profiler log for relevant testcase: ncalls  tottime  percall  cumtime  percall filename:lineno(function) 2969521/49877    3.871    0.000    4.753    0.000 test.py:51(__query) 1754305/50123    1.792    0.000    2.685    0.000 test.py:74(__update)       1721965    0.829    0.000    0.829    0.000 test.py:8(__init__)        983162    0.732    0.000    1.081    0.000 test.py:13(merge)       1619481    0.576    0.000    0.576    0.000 {built-in method min}        100002    0.548    0.000    0.551    0.000 {built-in method input}      262143/1    0.545    0.000    0.907    0.907 test.py:33(__build)             1    0.429    0.429    9.550    9.550 test.py:1(<module>)         49877    0.076    0.000    0.076    0.000 {built-in method print}        100002    0.068    0.000    0.068    0.000 {method 'rsplit' of 'str' objects}         49877    0.045    0.000    4.799    0.000 test.py:71(query)         50123    0.034    0.000    2.719    0.000 test.py:89(update)           339    0.002    0.000    0.002    0.000 {built-in method utf_8_decode}             1    0.002    0.002    0.908    0.908 test.py:25(__init__)           339    0.001    0.000    0.003    0.000 codecs.py:310(decode)             2    0.000    0.000    0.000    0.000 {built-in method __build_class__}             1    0.000    0.000    0.000    0.000 {built-in method init_builtin}I guess the problem is in query function. How can it be improved? Any ideas? Here is a relevant test-case. I need to achieve the result at least 2 times faster.
Segment tree in Python3
python;algorithm;python 3.x;tree
SegmentTreeNode objects have three attributes: left, right and value, but only value is ever used. Using plain integers instead of custom objects should speed things up, as it avoids overhead both in object creation and in attribute access.