0

我正在尝试在 python 中实现一个段树类。段树允许在对数时间内查询范围（更多关于段树）。在我的实现中，我持有必要的信息，以便能够回答 range 中元素的总和(i, j)。下面是我的代码。由于我是 python 新手，我仍然在每行末尾使用分号（继承自 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( );

构建函数应该从输入数组构建段树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

我不明白为什么序列的所有值都24在build函数退出之后。build调试信息在函数运行时显示了许多其他值，但在它退出后，所有值都神奇地变成了24. 为什么会这样？提前致谢。

4

1 回答 1

3

这将创建一个N*4元素列表：

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

但是，所有这些元素都是相同的Node。

例如，这将创建N*4不同Node的 s：

self.st = [Node(0) for i in range(N * 4)]
于 2013-04-21T19:31:08.393 回答