1. 序章

バイナリインデックスツリー（BIT）とも呼ばれるフェンウィックツリーは、要素を効率的に更新し、数値のリストの範囲の合計を計算できるデータ構造です。 このチュートリアルでは、可変範囲合計クエリの問題を解決するためにフェニックツリーを構築する方法を示します。

2. 問題の説明

可変範囲合計クエリの問題から始めましょう。 開始インデックスが。の数値の配列が与えられると、2つの演算があります：と。 演算の場合、インデックスの要素の値をに変更します。 演算の場合、位置と両端の間の数値の合計を計算します。 私たちの目標は、これら2つの操作を効率的に実装することです。

3. ブルートフォースソリューション

操作では、指定した場所の配列要素を直接更新できます。 この操作では、配列をインデックスからに繰り返し、各要素を合計できます。

このソリューションでは、操作に時間がかかり、操作に時間がかかります。 必要なスペースはです。

4. プレフィックス合計 解決

より高速な操作を行うために、 prefixsumアプローチを使用できます。 数値の入力配列の場合、インデックスでのプレフィックスの合計は、で終わるプレフィックス番号の合計です。

プレフィックス合計の定義に基づいて、2つのプレフィックス合計を使用して範囲合計を計算できます。

数値の配列が与えられた場合、最初に：からプレフィックス合計配列を作成しましょう。

操作では、2つのプレフィックス合計値を使用してクエリに直接回答できます。 ただし、操作のプレフィックス合計配列を更新する必要があります。

このソリューションでは、操作に時間がかかり、操作に時間がかかります。 スペース要件は、プレフィックスの合計を格納するための配列が必要なためです。

5. フェニック木 解決

ブルートフォースとプレフィックス合計のソリューションの場合、または操作には時間がかかります。 複数の操作がある場合、これら2つのソリューションには多くの時間がかかります。 たとえば、操作の数と操作がある場合、全体的な時間計算量は両方のソリューションになります。

フェニックツリーを使用すると、操作と操作の両方に時間がかかるだけなので、この問題をより効率的に解決できます。 したがって、操作の数と操作がある場合、全体的な時間計算量はになります。

5.1. 責任の範囲

操作を行うとき、更新要素の場所を示す入力インデックスパラメーター、があります。 同様に、操作を行う場合、で終わるプレフィックス番号の合計を示す入力インデックスパラメータ、があります。 フェニックツリーソリューションでは、入力インデックスのバイナリ形式に基づいて両方の操作を実行します。 これが、バイナリインデックスツリーとも呼ばれる理由です。

フェニックツリーでは、各インデックスにはさまざまな責任があります。 インデックスのバイナリ表現の右端のセットビット（RSB）の位置に基づいて、責任範囲の値を計算します。たとえば、のバイナリ表現はです。 の責任範囲は、RSBが値を与えるためです。 責任の範囲の別の例は、番号です。 の責任範囲は、RSBが値を与えるためです。

5.2. 責任計算の範囲

コンピュータサイエンスでは、 2の補数メソッドを使用して、正の数から負の数を生成します。 まず、正の数の2進表現の1と0を逆にします。 次に、1を追加します。したがって、ビット演算を使用して、インデックスの責任値の範囲を計算できます。

たとえば、8ビット形式ののバイナリ値はです。 各ビットを逆にすると、が得られます。 を追加すると、右から始まるすべてのビットは、元の正の数のRSBであるビットに到達するまで、次に高いビットにオーバーフローします。 したがって、を持つことができます。

2つの数値に対してビット単位のAND演算を実行すると、責任の範囲の値を取得できます。

インデックスの責任計算の範囲を定義しましょう：

5.3. フェニック木の構造

フェニックツリーソリューションの基本的な考え方は、各インデックスの責任範囲の合計を事前に計算することです。 次に、事前に計算されたFenwick値に基づいて、インデックスのプレフィックス合計を計算できます。 また、インデックスで要素を更新する場合、インデックスをカバーする事前に計算されたFenwick値のみを更新できます。

各インデックスの責任範囲の合計を示します。 配列の場合、次のような配列を持つことができます。

次の表は、1から16までの数値のフェンウィック値を示しています。

フェンウィック値の定義に基づいて、1つのフェンウィック値が複数のフェンウィック値をカバーできることがわかります。 たとえば、、、およびをカバーします。 ツリー構造を使用して、カバレッジの関係を表すことができます。

このフェンウィックツリー構造では、リーフノードがインデックス番号です。 各内部ノードは、子のFenwick値と独自のインデックス配列番号から構築できるFenwick値を表します。 例えば：

   

5.4. フェニック木の建設

フェンウィックツリーを構築するには、動的計画法を使用して、小さいフェンウィック値を大きいフェンウィック値に伝播します。

このアルゴリズムでは、最初にFenwick配列を入力配列で初期化します。 次に、ループを使用して、小さい方のFenwick値を親のFenwick値に伝播します。 時間計算量はです。

Fenwick配列を最初に作成する必要があるのは1回だけです。 将来的には、操作で更新する必要があるのは最大でFenwickの値だけです。

5.5. プレフィックス合計の計算

インデックスのプレフィックス合計を計算するとき、インデックスから開始して、次の値に達するまで下に進むことができます。

このアルゴリズムでは、入力インデックスから開始し、そのFenwick値をに追加します。 次に、のを削除し、新しいFenwick値をに追加します。 インデックスに到達するまで、このプロセスを続けます。

indexのプレフィックス合計を見つけたいとします。 まず、にを追加します。 次に、の値であるを減算し、新しいインデックスに到達します。 したがって、をに追加します。 ここでも、から減算して新しいインデックスを取得します。 同様に、にを追加します。 最後に、現在のインデックスから減算し、インデックスに到達したらループを停止します。

結局、私たちは持つことができます。

このアルゴリズムの時間計算量は、に達するまで各反復で元のインデックスの1セットビットを削除するためです。

5.6. フェニックツリーの更新

操作は操作の反対です。 入力インデックスから開始し、ツリーパスに沿って上に移動して、操作を伝播します。

場所に値を追加するとします。 最初にに追加できます。 次に、に基づいてその親を取得し、インデックスに到達します。 したがって、にも追加します。 同様に、配列サイズの境界に達するまで、のように親のFenwick値を更新し続けます。

と同様に、の時間計算量はです。

5.7. フェニックツリーソリューション

上記の関数を組み合わせて、可変範囲合計クエリの問題を解決できます。

この関数では、最初に更新された値を計算し、次に関数を呼び出してフェニック木を更新します。 時間計算量は、関数を1回だけ呼び出すためです。

関数では、関数を2回呼び出して、との間の合計を取得します。 全体的な時間計算量はまだです。

Fenwickソリューションのスペースの複雑さは、すべてのインデックスのFenwick値を格納する必要があるためです。

6. 結論

この記事では、フェニック木を使用して可変範囲の合計の問題を解決する方法を示しました。 フェニック木を使用すると、操作と操作の両方の時間を達成できます。