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.

• efimovgk: Yeah. You are right.This simple change speeds up code significantly. It can be said that the problem is solved.