区間木の実装と区間クエリ処理

区間木（Segment Tree）は、配列の区間に関するクエリを効率的に処理するためのデータ構造です。特に、範囲の合計、最小値、最大値などを求めるのに優れています。この教材では、区間木の基本的な実装と、区間クエリを処理する方法について学びます。

区間木の基本概念

区間木は、以下の特徴を持つデータ構造です：

• ノード: 各ノードは特定の区間を表し、その区間に関連する情報（合計、最小値、最大値など）を保持します。
• 葉ノード: 配列の各要素に対応する葉ノードがあります。
• 内部ノード: 親ノードはその子ノードの範囲の情報を集約します。

区間木の構築やクエリ処理は、通常O(log n)の時間で行うことができます。

区間木の実装

以下に、区間木の基本的な実装を示します。この実装では、配列の合計を計算するための区間木を構築します。

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (2 * self.n)
        self.build(data)

    def build(self, data):
        # 葉ノードを初期化
        for i in range(self.n):
            self.tree[self.n + i] = data[i]
        # 内部ノードを初期化
        for i in range(self.n - 1, 0, -1):
            self.tree[i] = self.tree[i * 2] + self.tree[i * 2 + 1]

    def update(self, index, value):
        # 葉ノードを更新
        index += self.n
        self.tree[index] = value
        # 内部ノードを更新
        while index > 1:
            index //= 2
            self.tree[index] = self.tree[index * 2] + self.tree[index * 2 + 1]

    def query(self, left, right):
        # [left, right) の合計を計算
        left += self.n
        right += self.n
        sum_value = 0
        while left < right:
            if left % 2 == 1:
                sum_value += self.tree[left]
                left += 1
            if right % 2 == 1:
                right -= 1
                sum_value += self.tree[right]
            left //= 2
            right //= 2
        return sum_value

コードの解説

1. 初期化: __init__ メソッドでは、配列のサイズを取得し、木を初期化します。
2. 木の構築: build メソッドでは、葉ノードを配列の要素で初期化し、内部ノードを合計で初期化します。
3. 更新: update メソッドでは、特定のインデックスの値を更新し、親ノードを再計算します。
4. クエリ: query メソッドでは、指定された区間の合計を計算します。

使用例

次に、区間木を使用して合計を計算する方法を示します。

if __name__ == "__main__":
    data = [1, 3, 5, 7, 9, 11]
    seg_tree = SegmentTree(data)

    # 区間 [1, 4) の合計を計算
    print("Sum of values in range [1, 4):", seg_tree.query(1, 4))  # 出力: 15

    # 値を更新
    seg_tree.update(1, 10)  # data[1] を 10 に更新

    # 区間 [1, 4) の合計を再計算
    print("Sum of values in range [1, 4) after update:", seg_tree.query(1, 4))  # 出力: 22

コードの解説

• data 配列を使用して区間木を作成します。
• query メソッドを呼び出して、区間 [1, 4) の合計を計算します。
• update メソッドを使用して、インデックス 1 の値を更新し、再度区間の合計を計算します。

まとめ

区間木は、範囲クエリを効率的に処理するための強力なデータ構造です。この教材では、基本的な実装と使用方法を学びました。区間木は、合計だけでなく、最小値や最大値を求めるためにも適用できるため、さまざまな問題に応用可能です。