フェンウィック ツリーのスロットの使用状況を追跡しているとします。例として、32 個のスロットを追跡することを考えてみましょう。以下の画像に示すように、フェンウィック ツリー レイアウトになります。グリッド内の数字は、基礎となる配列のインデックスを示し、カウントはフェンウィック ツリーによって操作されます。ここで、各セルの値は次のとおりです。そのセグメント内の「使用された」項目の合計 (つまり、配列セル 23 は [16-23] の範囲で使用されたスロットの量を格納します)。最下位レベルの項目 (つまり、セル 0、2、4、...) は、"1" (使用済みスロット) または "0" (空きスロット) の値のみを持つことができます。
私が探しているのは、指定された数の連続した空きスロットの最初の範囲を見つけるための効率的なアルゴリズムです。
説明のために、合計 9 つのスロットが使用されている下の画像に示されている Fenwick ツリーがあるとします (明るい灰色の数字はわかりやすくするために追加されているだけで、実際にはツリーの配列セルに格納されていないことに注意してください)。
ここで、たとえば、この範囲を見つける必要がある 10 個の空きスロットの最初の連続した範囲を見つけたいと思います。
これを行う効率的な方法を見つけることができないようで、少し頭痛の種になっています。必要なストレージ容量は私の目的にとって重要であるため、設計をセグメント ツリーに拡張したくないことに注意してください。
O(log N) タイプのソリューションに関する考えや提案は大歓迎です。
編集
バウンティ期間が終了した後の更新の時間。すべてのコメント、質問、提案、回答に感謝します。彼らは私に物事を再考させ、多くのことを教えてくれ、質問するときに解決したい問題にもっと焦点を合わせる必要があることを指摘してくれました。
@Erik Pは、要求された code/pseudo code を含む質問に対して妥当な回答を提供した唯一の人物だったため、報奨金を受け取ります。
彼はまた、この構造を使用した O(log N) 検索は不可能になるだろうと正しく指摘しました。最悪の場合のパフォーマンスについて考えさせられる証拠を提供してくれた@DanBjorgeに感謝します。
@EvgenyKluevのコメントと回答により、質問を別の方法で定式化する必要があることに気づきました。実際、私はすでに彼が提案したことの大部分を行っていました（https://gist.github.com/anonymous/7594508を参照- この質問を投稿する前に行き詰まった場所を示しています）、効率的な方法があることを期待してこの質問をしましたこれにより、この設計をセグメント ツリーに変更できなくなります (追加の 1024 バイトが必要になります)。しかし、そのような変更は賢明なことかもしれません。
興味のある方は、この質問で使用されている例に一致するバイナリ エンコードされたフェンウィック ツリー (64 ビットでエンコードされた 32 スロットのフェンウィック ツリー) をここで見つけることができます: https://gist.github.com/anonymous/7594245。