Segment tree in Python3

Question

I've implemented a Segment Tree in Python3:

import math

INF = 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.value


class 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.

Answer 1

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.