Java で非固定サイズのFenwick ツリーを実装する予定です。つまり、要素の追加/削除による範囲クエリのインターリーブを可能にする Fenwick ツリーです。
これまでに見たすべての実装とサンプルは、固定サイズの Fenwick ツリー用であり、周波数を前処理する前に要素の数がわかっています。固定サイズの配列を使用するため、前処理が完了した後に要素を追加または削除することはできません。（まあ、可能ですが、構造を再構築する必要があります）。
拡張するTreeMapか、おそらくを考えAbstractMapましたが、TreeMap実際には赤黒ツリーであるため、再調整プロセスに関与するノードの累積合計を失うことなく、赤黒メカニズムを実装する方法がわかりません (ツリーのバランスが保たれるようにするため)。 .
だから私はおそらく別のアプローチを取る必要があると思いました.単純なランダムアクセスを拡張または適応しArrayList、基になる配列のサイズが変更されたときにすべての累積合計を再計算してみませんか? これはもちろん影響がありますが、まさにそれが a のHashMap機能です。
これが、誰かがすでにそれを行っている場合に備えて、最初にここで質問し、どのアプローチが最善だと思うかを確認したかった理由です.