algorithm - セグメント ツリーの最悪の場合の実行時間

Question

セグメント ツリー O(logn) の範囲合計は最悪の場合?? O(n)じゃないの？範囲合計操作中に、アルゴリズムに従って左右のノードの両方をトラバースするとどうなるでしょうか?

Answer 1

active間隔に完全に含まれていないか、間隔によって完全にカバーされていない間隔を格納するノードをノードと呼びましょう。トラバースの各レベルに最大 2 つのアクティブなノードがあることは簡単にわかります。ノードがアクティブでない場合は、再帰する必要はありません。間隔が完全にカバーされている場合は、ノードに書き込まれた値を追加します。間隔が関心のあるものと交差しない場合は、単純にスキップします。したがって、アルゴリズムが実行する操作の数は、ツリーのレベルまたは の順序になりますO(log(n))。

Answer 2

最初のステップでは、左右のノードの両方をトラバースする必要があるかもしれませんが、その後の各ステップでは、片側のノードをトラバースするだけで済みます。それを見る別の方法は、見つけたい場合sum(n, m)（これが半開区間の合計を表すとしましょう[n, m)）、次のように計算できることに注意してください。

sum(n, m) = sum(0, m) - sum(0, n)

sum(0, n)とsum(0, m)それぞれの計算には対数時間がかかることに気付くでしょう。例えば、

sum(0, 13) = sum(0, 8) + sum(8, 12) + sum(12, 13)

ここで、右側の各用語はすでにセグメント ツリーに格納されています。