1

セグメント ツリーのような範囲合計を実行できるが、ツリー全体を再構築することなく、いつでも新しいデータの追加をサポートできるデータ構造を探しています。新しいデータの動的な追加を処理できるセグメントを一緒にハックできると思いますが、それはきれいではありません。

それが役立つ場合は、時間ベースであるため、常にデータを「追加」します。

例：

Order[time=0, quantity=1]
Order[time=1, quantity=2]
Order[time=2, quantity=4]
Order[time=3, quantity=2]

範囲合計セグメント ツリー:

                sum[0->3=9]
    sum[0->1=3]             sum[2->3=6]
time0=1     time1=2     time2=4     time3=2

追加した場合、上のツリーはどうなるでしょうかOrder[time=4, quantity=3]

                                        sum[0->4=12]
               sum[0->3=9]                                        sum[4->4=3]
    sum[0->1=3]           sum[2->3=6]                  sum[4->4=3]
time0=1     time1=2   time2=4     time3=2          time4=3

確かに上記のアプローチを使用できますが、もっと良い方法があることを願っています。

4

2 に答える 2

1

連続した時間値で常にデータを追加する場合は、すべての数量の累積合計を配列に格納することを検討できます。

1,2,4,2 の例では、配列は 1,3,7,9 になります。

1
1+2=3
1+2+4=7
1+2+4+2=9

次に、累積配列の 2 つの要素を減算することにより、要素の範囲にわたって値の合計を実行できます。

これは、追加の場合は O(1)、範囲合計の場合は O(1) です。

于 2013-11-04T20:08:36.413 に答える
1

あなたの問題を完全に理解しているかどうかはわかりませんが、 Fenwick treeを探しているようです。で配列からフェンウィック ツリーを構築できますnlog(n)。これらは、で連続した範囲の合計を可能にしlog(n)、でノードを更新できますlog(n)。配列の拡張についてはわかりません。私はそれを試したことはありませんが、それlog(n)も同様だと思います。

于 2013-11-04T20:14:44.147 に答える