I am trying to implement a segment tree class in python. Segment trees allow queries on ranges in logarithmic time (more about segment trees). In my implementation I hold the necessary information to be able to answer the sum of the elements in a range (i, j). Below there is my code. As I am new to python, I still use the semicolon at the end of each line (inherited from C++).
class Node :
val = 0;
def __init__( self, _val ) :
self.val = _val;
class ST :
st = [];
def __init__( self, N ) :
self.st = [ Node( 0 ) ] * N * 4;
def build( self, nd, lo, hi, a ) :
print "build( self, {0}, {1}, {2}, {3})".format( nd, lo, hi, a );
if lo == hi :
print "setting self.st[{0}] to {1}".format( nd, a[ lo ] );
self.st[ nd ].val = a[ lo ];
print "done! now self.st[", nd, "] is ", self.st[ nd ].val;
else :
print "else statement for nd = {0}".format( nd );
self.build( nd*2+1, lo, int( ( lo+hi )/2 ), a );
self.build( nd*2+2, int( ( lo+hi )/2+1 ), hi, a );
self.st[ nd ].val = self.st[ nd*2+1 ].val + self.st[ nd*2+2 ].val;
print "self.st[{0}] is set to {1}".format( nd, self.st[ nd ].val );
def echo( self ) :
for i in self.st :
print i.val;
def main( ) :
tree = ST( 5 );
a = [ 2, 3, 4, 5, 6 ];
tree.build( 0, 0, 4, a );
tree.echo( );
main( );
The build function is supposed to build the segment tree from the input array a. When I run the program, I get the following output:
build( self, 0, 0, 4, [2, 3, 4, 5, 6])
else statement for nd = 0
build( self, 1, 0, 2, [2, 3, 4, 5, 6])
else statement for nd = 1
build( self, 3, 0, 1, [2, 3, 4, 5, 6])
else statement for nd = 3
build( self, 7, 0, 0, [2, 3, 4, 5, 6])
setting self.st[7] to 2
done! now self.st[ 7 ] is 2
build( self, 8, 1, 1, [2, 3, 4, 5, 6])
setting self.st[8] to 3
done! now self.st[ 8 ] is 3
self.st[3] is set to 6
build( self, 4, 2, 2, [2, 3, 4, 5, 6])
setting self.st[4] to 4
done! now self.st[ 4 ] is 4
self.st[1] is set to 8
build( self, 2, 3, 4, [2, 3, 4, 5, 6])
else statement for nd = 2
build( self, 5, 3, 3, [2, 3, 4, 5, 6])
setting self.st[5] to 5
done! now self.st[ 5 ] is 5
build( self, 6, 4, 4, [2, 3, 4, 5, 6])
setting self.st[6] to 6
done! now self.st[ 6 ] is 6
self.st[2] is set to 12
self.st[0] is set to 24
24
24
24
24
24
24
24
24
24
24
24
24
24
24
24
24
24
24
24
24
I can't understand why all the values of the sequence are 24 after the build function exits. The debug information show many other values while the build function is running, but after it exits, all the values magically turn into 24. Why is this happening? Thanks in advance.
This creates a list of N*4 elements:
self.st = [ Node( 0 ) ] * N * 4;
All these elements are the same one Node though.
This, for instance, will create N*4 different Nodes:
self.st = [Node(0) for i in range(N * 4)]