# Segment tree in Python3

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.

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.

• Yeah. You are right.This simple change speeds up code significantly. It can be said that the problem is solved. Apr 27, 2014 at 5:44