2013-04-21 26 views
0

我想在python中實現一個段樹類。分段樹允許查詢對數時間範圍(more about segment trees)。在我的實施中,我持有必要的信息以能夠回答(i, j)範圍內的元素總和。下面是我的代碼。由於我是python的新手,我仍然在每行的末尾使用分號(從C++繼承)。python中的簡單代碼導致意外的行爲

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(); 

構建函數應該從輸入數組a構建分段樹。當我運行該程序,我得到下面的輸出:

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 

我不明白爲什麼該序列的所有值都build函數退出後24。調試信息顯示許多其他值,而build函數正在運行,但在它退出後,所有值神奇地變爲24。這是爲什麼發生?提前致謝。

回答

3

這將創建N*4元素的列表:

self.st = [ Node(0) ] * N * 4; 

所有這些元素都是相同的一個Node雖然。

此,例如,將創建N*4不同Node S:

self.st = [Node(0) for i in range(N * 4)] 
+0

謝謝!它的工作... – 2013-04-21 19:36:46

+0

嘗試在修復之前和之後打印self.st以查看差異 – Benjamin 2013-04-21 19:37:22