C ++のバイナリインデックスツリーまたはフェンウィックツリー？

数値のフラット配列と比較する場合、フェンウィックツリーは、要素の更新とプレフィックスの合計の計算という2つの操作の間ではるかに優れたバランスを実現します。 m個の数値のフラット配列の場合、要素またはプレフィックスの合計を格納できます。最初のインスタンスの場合、プレフィックスの合計を計算するには線形時間が必要です。 2番目のインスタンスの場合、配列要素の変更または更新には線形時間が必要です（どちらの場合も、他の操作は一定時間で実行できます）。フェニック木は、両方の操作をO（log m）時間で実行できるようにします。これは、数値をツリーとして表すことによって取得されます。各ノードの値は、そのサブツリー内の数値の合計として扱われます。ツリー構造により、O（log m）ノードアクセスのみを使用して操作を実行できます。

1ベースの配列を検討することにより、フェニック木が最も簡単に理解されます。インデックスjが2の累乗である各要素には、最初のj要素の合計が含まれます。インデックスが2の2の（異なる）累乗の合計を示す要素は、前の2の累乗以降の要素の合計で構成されます。基本的に、各要素は、ツリー内の親以降の値の合計で構成され、その親は次のようになります。インデックスの最小または最下位ビットをクリアすることで検出されます。

任意の位置またはインデックスまでの合計を計算するには、位置またはインデックスのバイナリ展開を検討し、バイナリ形式の各1ビットに対応する要素を追加します。

たとえば、最初の11個の値の合計を計算したいとします。 11はバイナリで1011です。これは3つの1ビットで構成されているため、1000、1010、および1011の3つの要素を追加する必要があります。これらはそれぞれ値1〜8、9〜10、および11の合計で構成されます。

簡単なCの実装が続きます。

例

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the minimum or least significant one
int A1[SIZE];
int sum(int i) // Returns the sum from index 1 to i{
   int sum = 0;
   while (i > 0)
   sum += A1[i], i -= LSB(i);
   return sum;
}
void add(int i, int k) // Adds k to element with index i{
   while (i < SIZE)
   A1[i] += k, i += LSB(i);
}