arrays - バイナリ インデックス ツリーの作成

Question

私はBITに関するさまざまなチュートリアルを読みました..トップコーダーなどのチュートリアルで、すべての操作はそれらで十分に説明されていますが、BITの作成方法がわかりません.

1-D の配列が与えられた場合、対応する BIT をどのように計算する必要があるでしょうか? 元。配列が 10 8 5 9 1 の場合、これの BIT は何になりますか?

私は初心者なので、私の質問がばかげているように聞こえる場合は申し訳ありませんが、これを理解していません。だから、助けてください。

Answer 1

空の構造 (allo 0) から始めて、各要素を挿入するだけです。複雑さは O(NLogN) ですが、アルゴリズムの残りの部分も NLogN である可能性が高いため、問題にはなりません。