なぜセグメントツリーはBT

Question

の代わりに配列を使って実装されているのですか？セグメントツリーの実装には疑問があります。なぜセグメントツリーは、バイナリツリーではなく、配列を使って実装されているのですか？

もし配列を使って実装すれば、何のメリットがあり、バイナリツリーとして実装すれば問題はありますか？配列を使って実装するには、左の子関数を2 * i + 1、右の子関数を2 * i + 2として使用する必要があります。バイナリツリーとして実装する場合、単純にnode - > lft & node-> rhtを実行できます。しかし、何が問題なのですか？ありがとう

Answer 1

利点は密度です。配列は内容と同じくらいのスペースをとります。バイナリツリーの場合、各ノードにメモリ管理オーバーヘッドがあります。子ポインタに余分なスペースも必要です。また、配列は通常は連続したメモリ位置にありますが、ツリーノードはヒープ全体に分散する可能性があります。つまり、メモリキャッシュが役立たない可能性があります。