8

質問: 累積和を簡単に計算できる Fenwick ツリー (バイナリ インデックス ツリー) を偶然見つけました。ただし、リーブ (被加数) の数が一定である実装のみを見つけました (ただし、その値は変更される可能性があります)。リーブ (加数) の数を変更できる、つまり可変サイズを持つ一般化されたフェンウィック ツリーのようなものはありますか?

背景 現在、いくつかの確率的シミュレーション コードを (C++ で) 書いています。壷にはボールがあり、各ボール i には特定の確率 p_i が描かれます。描画イベントが発生すると、ボールが描画 (および削除) され、新しい確率を持つ 2 つの新しいボールに置き換えられます (すべての確率はそれに応じて再スケーリングされます。この「再スケーリング」は既に効率的に行われているので、気にしないでください)。ある時点で、ボールの数が一定値 (以前にわかっている) の周りで変動するように、ボールを削除し始めます。描画を効率的に行うために、二分木を使用したいと考えています。標準の Fenwick ツリーは、骨壷内のボールの数を変更できないことを除いて、まさに私が望むことを行います。

典型的な数 10 個のボールから始め、ボールを追加し、約 1000 個になったらボールを​​削除し始め、その後 900 個から 1100 個のボールが骨壷に収まるようにします (つまり、ボールの数が約 1000 個に留まるようにボールを追加および削除します)。

これまでの回避策 必要なボールの最大数を見積もり (ある程度のセキュリティ マージンを考慮して、たとえば 1200 個のボール)、固定サイズの Fenwick ツリーを大きくして、最初はほとんどのボールが描画される確率が 0 であり、連続的に更新されます。

ご助力ありがとうございます！マティアス

4

1 に答える 1

12

実際、通常の (決して一般化されていない) フェンウィック ツリーでは、いつでも葉の数を増やすことができます。

一部の特定の実装では、それが許可されない場合があります。しかし、これは修正される可能性があります。たとえば、TopCoder からの実装では、葉の数を変更できません。問題は、update関数が指定されたインデックスから開始して上に向かって配列要素を変更し、制限 ( ) に達したときに停止することMaxValです。これは、この場合事前にはわかりません。read関数は配列要素を下方向に反復するため、現在の配列サイズを知る必要はありません。との間で配列反復コードを交換するupdateとread、この問題が修正される可能性があります。現在、を知る必要はupdateありません。MaxValMaxValreadMaxVal

int read(int idx){
    int sum = 0;
    while (idx <= MaxVal){
        sum += tree[idx];
        idx += (idx & -idx);
    }
    return sum;
}

void update(int idx ,int val){
    while (idx > 0){
        tree[idx] += val;
        idx -= (idx & -idx);
    }
}

ノート。

  1. TopCoder (read接頭辞の合計を返す) からの実装とは異なり、この実装は接尾辞の合計を返します。前置合計が必要な場合はread、値の合計から返された値を差し引くだけです。
  2. この実装を選択したのは、(1) よく知られている TopCoder の実装を単純に変更したものであり、(2) 非常に対称的な方法でインデックスを更新するため、接頭辞から取得するには '+' を '-' に変更するだけで十分だからです接尾辞に。
  3. それ以外の場合は、インデックスの計算で別のビット演算を使用することをお勧めします。IMHO this blog: Fenwick trees demystifiedは、インデックスの更新ごとに 3 つではなく 2 つの操作のみを使用する、より良い代替案を提案しています (ただし、可変サイズを許可するためにいくつかの変更も必要です)。互換性が問題にならない場合は、BLSR最近の Intel の命令セット (BMI1) などの特定の命令を使用することで、さらにうまくいく可能性があります。
于 2014-02-24T19:09:31.793 に答える