Fenwick木の基本操作と用途

Fenwick木（またはバイナリインデックスツリー）は、配列の要素に対する累積和を効率的に計算するためのデータ構造です。このデータ構造を使用することで、更新とクエリの両方をO(log n)時間で行うことができます。ここでは、Fenwick木の基本操作とその用途について詳しく学びます。

Fenwick木の基本操作

Fenwick木を実装するためには、以下の基本的な操作を理解する必要があります。

1. 要素の更新: 配列の特定の要素を更新します。
2. 区間の累積和の計算: 配列の特定の範囲の合計を計算します。
3. 初期化: Fenwick木を初期化します。

Fenwick木の実装

以下に、Fenwick木の基本的な実装を示します。この実装では、要素の更新と区間の累積和の計算を行います。

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, value):
        """index位置の値をvalueだけ更新します。"""
        while index <= self.size:
            self.tree[index] += value
            index += index & -index

    def query(self, index):
        """0からindexまでの累積和を返します。"""
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

    def range_query(self, left, right):
        """leftからrightまでの範囲の累積和を返します。"""
        return self.query(right) - self.query(left - 1)

コードの解説

1. 初期化:

2. __init__メソッドでは、サイズを指定してFenwick木を初期化します。内部配列treeは0で初期化されます。

3. 要素の更新:

4. updateメソッドでは、指定したindexに対してvalueを加算します。indexは1から始まるため、配列のインデックスと操作が一致するように注意が必要です。

5. 累積和の計算:

6. queryメソッドは、0から指定されたindexまでの累積和を計算します。ビット演算を利用して、更新された値を効率的に取得します。

7. 範囲の累積和の計算:

8. range_queryメソッドでは、指定した範囲の累積和を計算します。これは、queryメソッドを利用して計算されます。

使用例

次に、Fenwick木を使った具体的な使用例を示します。

# Fenwick木の使用例
if __name__ == "__main__":
    # 配列のサイズ
    n = 10
    fenwick_tree = FenwickTree(n)

    # 配列の要素を更新
    fenwick_tree.update(1, 5)  # index 1に5を加算
    fenwick_tree.update(2, 3)  # index 2に3を加算
    fenwick_tree.update(3, 7)  # index 3に7を加算

    # 累積和のクエリ
    print("1から3までの累積和:", fenwick_tree.range_query(1, 3))  # 5 + 3 + 7 = 15
    print("1から2までの累積和:", fenwick_tree.range_query(1, 2))  # 5 + 3 = 8

    # 要素を更新
    fenwick_tree.update(2, 2)  # index 2の値を2増加

    # 再度累積和のクエリ
    print("1から3までの累積和（更新後）:", fenwick_tree.range_query(1, 3))  # 5 + 5 + 7 = 17

使用例の解説

この使用例では、次のことを行っています：

1. Fenwick木をサイズ10で初期化します。
2. 要素を更新し、特定のインデックスに値を加算します。
3. 指定した範囲の累積和を計算し、結果を表示します。
4. 要素を再度更新し、変更後の累積和を確認します。

Fenwick木の用途

Fenwick木は、以下のような多くの用途があります。

• 累積和の計算: 配列の累積和を効率的に計算できます。
• 頻繁な更新がある場合のデータ処理: 動的なデータに対して、更新とクエリを効率的に行うことができます。
• 数列の逆数や最小値の計算: 統計的な計算にも利用されることがあります。

Fenwick木は、特に数値の更新や累積和の計算が頻繁に行われる場合に非常に有用なデータ構造です。これにより、複雑な計算を効率的に行うことが可能になります。