algorithm - 開く - 累積値を保持するのに適したデータ構造は何ですか?




undefined columns selected 意味 (5)

累積値を保持するコレクションにアクセスするときに非常に効率的なアイデア、概念、または実績のあるデータ構造を探しています。

例は私の必要性にもっと光を当てるかもしれません:

値のリストがあります(2,3,5)。 累積値を見ると、このリストは(2,5,10)になります。

リストの先頭に1を加えて(1,2,3,5)と累積用語で(1,3,6,11)を得ます。

私は累積値を見る必要があるだけです、私は1,2,3,5に全く興味がありません。 位置にすばやく挿入し、位置を削除すると、累積配列をすばやく更新できるはずです(理想的には、配列全体を反復処理して値を再計算することなく)。

何かアイデアやヒントは?

@Kristo(コメントを入れるには長すぎる):負の数がなぜ合計値を意味のないものにするのかを明確にするために、この例に従ってください。

1を挿入し、その後に-1を挿入します。 合計は0より1です。(1、-1)//(1,0)3を挿入してから-3を挿入する。 Sumは3、次に0です。(1,3、-1、-3)//(1,4,3,0)2を挿入してから-2を挿入します。 合計は2で0です。(1,3,2、-1、-2、-3)//(1,4,6,5,3,0)

私の「魔法の数」が4であれば、それを超えたかどうかはわかりません。

シモンズ:これの主な理由は、私がある値を超えたかどうか、そしてチェーンのどこにあるかを見分けることができることです。


C#では、実際の値をすべてリストに保持し、カスタムの反復子を使用して累積値をループします。

あなたは、イテレータがあなたがあなたの限界を越えたことをあなたに告げるところまでしか再計算しないでしょう(明らかに、あなたはそれのためにコードを書かなければならないでしょう)。

私は値がリストを反復する時が来るまで何の計算もすることなくあなたが追加/削除できることであると思います(私はあなたがカットオフ数を見つけるためにとにかくする必要があると思います)。



ノードがそれらのサブツリーの合計を含むという追加の特性を持つ二分探索木を使用してください。 すべての操作はまだO(lg n)です。 値を挿入または削除するには、通常の手順を実行し、さらにすべての親の合計を更新します。 合計を取得することは、要素を含むノードを見つけて、その合計から正しい子の合計を引いたものを返すのと同じくらい簡単です。


私が考えることができる唯一の最適化は累積的なリストの '怠惰な'評価をすることです。

ソース値のリストに加えて、正確な累積リストの最も高い位置の番号を追跡します。 それよりも大きい数値が必要な場合は、リストを調べて値とインデックスを更新します。

idx  values       cumulative    operation
 3   (2,3,5)      (2, 5, 10)
 0   (1,2,3,5)    (X,X,X,X)     insert 1 at 0 
 3   (1,2,3,5)    (1,3,6,X)     look for value over 5     
 3   (1,2,3,5,4)  (1,3,6,X,X)   insert 4 at 4 

もちろん、リストの最初の方にアイテムを追加しているのであれば、これはあまり役に立ちません。


  • バイナリインデックスツリーの累積頻度のデータ構造を見ることができます。
  • 値の範囲を固定のビット範囲に分割することができます。 例 3間隔

    #define NUM (1<<24)  // max value in your data set
    #define BITS0 8
    #define BITS1 8
    int cum0[NUM >> (BITS0+BITS1)]; // sum of cum1
    int cum1[NUM >> BITS1]; // sum of count
    int count[NUM];
    
    int add(id, val) { // add a value
      cum0[id >> (BITS0+BITS1)] += val;
      cum1[id >> BITS1] += val; 
      count[id] += val;                     
    }
    
    int cumvalue(int id) { int cum = 0; // return cum value at index id         
      for(i = 0; i < (id >> (BITS0+BITS1));i++) cum += cum0[i]; i <<= BITS0;
      for(i = (id & ~((1 << (BITS0+BITS1))-1)) >> BITS1; i < (id >> BITS1); i++) cum+= cum1[i]; i <<= BITS1;
      for(i = id & ~((1 << BITS1) -1); i < id; i++) cum += count[i];            
      return cum;
    }
    






data-structures