0

Python でセグメント ツリー クラスを実装しようとしています。セグメント ツリーを使用すると、対数時間の範囲でクエリを実行できます (セグメント ツリーの詳細については、 を参照してください)。私の実装では、範囲内の要素の合計に答えるために必要な情報を保持しています(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( );

build 関数は、入力配列からセグメント ツリーを構築することになっています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。

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