問題タブ [fenwick-tree]

BIT の仕組みを知っています。しかし、ビットを使用して完全な範囲内の最小/最大要素を見つけることができるか、より具体的には、すべての更新プロセスが完了した後に最小 (または最大) 値を見つけることができるかどうか疑問に思っていました。これはセグメント ツリーを使用して非常にうまく達成できることはわかっていますが、BIT を使用して同じことを行うことは可能ですか?

ありがとう。

PS: 完全な BIT をトラバースし、各インデックスの値を計算する明白な方法を知っています。より効率的/最適化された方法を探しています。

フェンウィック ツリーのスロットの使用状況を追跡しているとします。例として、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。

Spoj で D クエリの問題を解決しようとしています。http://www.spoj.com/problems/DQUERY/ 設定して結果を記憶することを考えていますが、それは本当に遅いです。そのため、バイナリ インデックス ツリーが 1 つのクエリの lgN を取得するのに役立つと考えていましたが、それで解決策を考えることはできません。誰でも私を助けることができますか？

n 個の空の箱が一列に並んでいるとしましょう。コインのm 個のグループを、事前にわかっているいくつかの連続したボックスに入れます。コインの最初のグループをi_1からj_1までのボックスに入れ、2 番目のグループをi_2からj_2までのボックスに入れます。

すべてのコインをボックスに入れた後、ボックスiのコインの数をc_iとする。インデックス i = s, s + 1, ... e - 1, eのボックスにいくつのコインがあるかをすばやく判断できるようにしたい、つまり、合計を計算したい

効率的。これはFenwick treeを使用して行うことができます。改善がなければ、Fenwick ツリーはc_iを格納するためのO(n)スペース(実際には、tree[i] != c_i、値はよりスマートに格納されます) と、上限の合計を計算するための O(log n) 時間を必要とします。

場合があれば

• nは、長さnのテーブルを作成するには大きすぎます(たとえば、〜 10 000 000 000 としましょう)
• mは十分に小さい (たとえば ~ 500 000 としましょう)

ボックスの座標 (インデックス) を何らかの形で圧縮する方法があります。つまり、インデックスi_1、i_2、... 、i_mを持つボックスだけを格納するだけで十分です。tree[i]に格納される値はiのバイナリ表現に依存するため、インデックスi_1、j_1、i_2、j_2、 ... 、i_m、j_mをソートし、長さO(m)のツリーを作成します。ツリーに新しい値を追加するのは簡単です。また、その合計を計算するには、 eより大きくない最初のインデックスを見つけるだけです。sよりも小さくない最後のもの。どちらもバイナリ検索で実行できます。その後、合計は簡単に計算できます。

問題は 2D の場合に発生します。ここで、平面内に点(x,y)の領域0 < x,y < n があります。その領域にはm 個の長方形があります。それらの左下隅と右上隅の座標がわかっているので、点(a,b) を含む四角形の数を計算したいと考えています。最も単純な (そして私の唯一の) アイデアは、1D の場合の方法に従うことです。コーナーの座標x_iごとに、コーナーのすべての座標y_iを格納します。O(m^2) =あまりにも多くのスペースが必要なので、このアイデアはあまり賢くありません。私の質問は

フェンウィック ツリーを使用した問題の解決策が推奨されますが、すべての解決策を歓迎します。

アルゴリズムの問​​題の解決策を理解するのに苦労しています

特に、コードのこの部分の方法や理由がわかりません

各ポイントの左下象限にあるポイントの総数を計算できます。

誰か詳しく教えてください。

遅延伝播による配列の特定のセグメントへの定数の追加または AP の追加を含むセグメント ツリーで範囲更新を行う方法と、特定のセグメントの合計についての後続のクエリを作成する方法を知っていますが、幾何級数。

同じ漸近時間複雑度でセグメントツリーを使用することで、これをどのように達成できます(log(N))か?

たとえば、配列が :
a[1], a[2], .... , a[l],a[l+1]...a[r-1], a[r] ... a[n - 1], a[n] で、[l, r] を公比 d で更新すると、更新された配列は次のようになります。 a[1], a[2], .... , a[l] + d, a[l+1] + d^2 ...a[r-1] + d^(l-r), a[r] + d^(l-r+1) ... a[n - 1], a[n]

また、log(n) の任意のセグメントの合計についてもクエリを実行できるはずです。

Java でフェンウィック ツリーを実装しようとしましたが、期待どおりの結果が得られません。これが私のコードです：

私が入力するとき：

10
1 2 3 4 5 6 7 8 9 10

私は得る：

13
19

したがって、インクリメント機能は正常に機能します。ただし、query(4) は、インデックス 4 までの累積合計を提供する必要があります。

(1 + 2 + 13 + 4 + 5) = 25