セグメント木

説明

I を区間、あるいは線分の集合とする。p₁, p₂, ..., p_mを、左から右に並べられた、異なる区間の端点のリストとする。これらの点によって誘導される実数直線の分割を考える。この分割の各領域を「基本区間（elementary intervals）」と呼ぶ。したがって、基本区間は左から順に以下のようになる。

${\displaystyle (-\infty ,p_{1}),[p_{1},p_{1}],(p_{1},p_{2}),[p_{2},p_{2}],\dots ,(p_{m-1},p_{m}),[p_{m},p_{m}],(p_{m},+\infty )}$

つまり、基本区間のリストは、隣接する2つの端点 p_i と p_i+1 の間の開区間と、単一の端点からなる閉区間が交互に並んだものとなる。単一の点は、それ自体が区間として扱われる。なぜなら、クエリへの回答は、基本区間の内部とその端点で必ずしも同じになるとは限らないからである。^[3]

区間の集合 I が与えられたとき、I に対するセグメント木 T は次のように構成される。

• T は二分木である。
• その葉は、I の端点によって誘導される基本区間に、順序通りに対応する。すなわち、一番左の葉は一番左の区間に対応し、以下同様である。葉 v に対応する基本区間を Int(v) と記す。
• T の内部ノードは、基本区間の和集合である区間に対応する。ノード N に対応する区間 Int(N) は、N を根とする部分木の葉に対応する区間の和集合である。これは、Int(N) がその2つの子ノードの区間の和集合であることを意味する。
• T の各ノードまたは葉 v は、区間 Int(v) と、何らかのデータ構造に格納された区間の集合を保持する。ノード v のこの正準サブセット（canonical subset）には、I に含まれる区間 [x, x′] のうち、Int(v) を含み、かつ Int(parent(v)) を含まないものが格納される。つまり、T の各ノードは、自身の区間を完全に覆うが、親の区間は完全に覆わないセグメントを格納する。^[4]

構築

セグメントの集合 I からのセグメント木の構築は、以下のように行われる。まず、I に含まれる区間の端点がソートされる。それによって基本区間が得られる。次に、基本区間を元に平衡二分木が構築され、各ノード v について、それが表す区間 Int(v) が決定される。残るは各ノードの正準サブセットの計算である。これを達成するために、I の区間が一つずつセグメント木に挿入される。区間 X = [x, x′] は、以下の手順を用いて、T を根とする部分木に挿入できる。^[5]

• Int(T) が X に含まれるなら、X を T に格納して終了する。
• そうでない場合：
  • X が T の左の子の区間と交差するなら、再帰的に X をその子に挿入する。
  • X が T の右の子の区間と交差するなら、再帰的に X をその子に挿入する。

構築操作全体には ${\displaystyle O\left(n\log n\right)}$ の時間がかかる。ここで n は I に含まれるセグメントの数である。

クエリ

セグメント木に対するクエリは、点 q_x（木の葉の一つであるべき）を受け取り、その点 q_x を含む格納されたすべての線分のリストを取得する。

形式的に述べると、ノード（部分木）v とクエリ点 q_x が与えられたとき、クエリは以下のアルゴリズムを用いて実行できる。

1. I(v) に含まれるすべての区間を報告する。

1. v が葉でない場合：

1. • q_x が Int(v の左の子) に含まれるなら
     • 左の子に対してクエリを実行する。
   • q_x が Int(v の右の子) に含まれるなら
     • 右の子に対してクエリを実行する。

n個の区間を含むセグメント木において、与えられたクエリ点を含む区間は ${\displaystyle O\left(\log n+k\right)}$ の時間で報告できる。ここで k は報告された区間の数である。

記憶領域の要件

n個の区間の集合 I に対するセグメント木 T は、${\displaystyle O\left(n\log n\right)}$ の記憶領域を使用する。

集合 I には最大 4n + 1 個の基本区間がある。T は最大 4n + 1 個の葉を持つ平衡二分木であるため、その高さは ${\displaystyle O\left(\log n\right)}$ である。任意の区間が木の特定の深さで格納されるのは最大2回までであるため、記憶領域の総量は ${\displaystyle O\left(n\log n\right)}$ となる。^[6]

高次元への一般化

セグメント木は、多段セグメント木の形で、より高次の次元空間へと一般化できる。高次元版において、セグメント木は軸に平行な（超）矩形の集合を格納し、与えられたクエリ点を含む矩形を取得できる。この構造は ${\displaystyle O\left(n\log ^{d}n\right)}$ の記憶領域を使用し、クエリには ${\displaystyle O\left(\log ^{d}n\right)}$ の時間で回答する（dは次元数を表す）。

フラクショナルカスケーディング（英語版）を用いることで、クエリ時間の境界を対数係数分だけ下げることができる。関連する構造の最も深いレベルで区間木を用いることで、記憶領域の境界を対数係数分だけ下げることができる。^[7]

モノイドに対するセグメント木の構成

セグメント木は線分集合の和集合だけでなく、閉じた演算を持ち、結合法則を満たし、単位元を持つ集合であれば構築することができる（上記例の線分集合 I もこの性質を満たす）。^[8] このような代数的構造をモノイドといい、モノイドに対してセグメント木を構成することで、整数・文字列・行列などの集合に対して以下のようなクエリを処理することができる。

さらに見る , ...

具体的な演算とモノイドの対応例

クエリの種類	演算内容 (⋅)	単位元 (e)	備考
範囲合計 (RSQ)	加算 (+)	0	-
範囲最小値 (RMQ)	${\displaystyle \min(a,b)}$	∞	LCA問題の解決などに使用
範囲最大値 (RMQ)	${\displaystyle \max(a,b)}$	−∞	最小値と同様の性質を持つ
範囲積	乗算 (×)	1	逆元が存在しない場合も処理可能
範囲論理演算	AND, OR, XOR	1,0,0	ビット単位の操作に適する
範囲行列積	行列の積	単位行列 I	非可換だが結合法則は成り立つ

閉じる

つまり、集合を配列のような順序のあるデータ構造で持つとすると、以下の操作を時間計算量 ${\displaystyle O\left(\log n\right)}$ で行うことができる。

• ${\displaystyle i}$番目の要素に${\displaystyle x}$を代入
• ${\displaystyle i}$番目の要素を取得
• ${\displaystyle l}$番目の要素から${\displaystyle r}$番目の要素のモノイド積を計算

セグメント木において、演算が可換である必要はない。例えば行列の積は ${\displaystyle A\cdot B\neq B\cdot A}$ だが、結合法則さえ成り立てばセグメント木で扱うことが可能である。この性質は、動的なグラフの連結性判定や線形変換の合成などで有用である。

完全二分木による表現

セグメント木を構築する際、管理対象となる配列のサイズをnとすると、葉ノードの数はn以上の最小の2の冪数N（2k≥n）に調整されることが一般的である。 これにより、木は完全二分木となり、インデックス管理が容易になる。

1-indexed（根ノードのインデックスを 1 とする）の実装では、あるノードiに対して以下の関係が成り立つ 。

• 左の子ノード: ${\displaystyle 2i}$（i << 1）
• 右の子ノード: ${\displaystyle 2i+1}$（i << 1 | 1）
• 親ノード: ${\displaystyle i/2}$ （整数除算）（i >> 1）

つまりある位置xにある要素が左の子ノードであれば、その要素の右の子ノードはx+1、親ノードは x/2の位置にあると計算できる。ある要素が左右どちらの子ノードなのかは、その要素の位置の偶奇を確かめればいい。1-indexedの実装の場合、要素の位置が奇数なら右、偶数なら左の子ノードに相当する。 この構造により、ビット演算を利用した高速なノード移動が可能となる 。

空間計算量とメモリ消費の詳細

セグメント木に必要なメモリ量は、最悪の場合で元の配列サイズの約4倍となる。具体的に、n 個のデータを格納するために必要なノード数は次のように見積もられる。

1. 葉ノードの数: ${\displaystyle N=2^{k}}$（n 以上で最小の2の冪数）
2. 内部ノードの数: ${\displaystyle N-1}$
3. 合計ノード数: ${\displaystyle 2N-1}$

n が 2^k+1 のとき、N は 2^k+1となり、合計ノード数は約 4nに達する^{[注 1]}。そのため、要素数4nで配列を確保するのが通例である^{[注 2]}。一方で、2の冪数に切り上げない実装や、ボトムアップな反復的実装を用いることで、メモリ消費を 2n 程度に抑える手法も存在する。^[10]

基本操作の詳細アルゴリズム

セグメント木の主要な操作は「構築」、「一点更新」、「範囲クエリ」の三つである。これらの操作はすべて、木の高さ ${\displaystyle H=\log 2N}$ に依存する計算量を持つ。

class SegmentTree:
    """
    配列に対して「一点更新」と「区間計算」を O(log N) で行うデータ構造。
    モノイド（結合則を満たし、単位元を持つ演算）を対象とする。
    例: 区間和、区間最小値(RMQ)、区間最大値、区間最小公倍数など。
    """
    __slots__ = ("n", "fold_op", "log", "tree_size", "tree")

    def __init__(self, n: int, fold_op, e_fold) -> None:
        """
        n: 要素数
        fold_op: モノイド積：二項演算（例：min, max, sumなど）
        e_fold: 単位元（演算に影響を与えない値。例：sumなら0, minなら無限大）
        """
        self.n = n 
        self.fold_op = fold_op 
        self.log = (n - 1).bit_length()
        # tree_size: 葉の数（n以上の最小の2べき）
        self.tree_size = 1 << self.log 
        # tree: 全ノードを格納する配列。サイズは tree_size * 2
        # インデックス1が根、tree_size以降が葉になる
        self.tree = [e_fold] * (self.tree_size << 1) 

    @classmethod
    def from_array(cls, init_arr: list, fold_op, e_fold) -> "SegmentTree":
        """ 初期配列からセグメント木を構築する / O(N) """
        ins = cls(len(init_arr), fold_op, e_fold)
        # 葉の部分（後半）に初期データをコピー
        ins.tree[ins.tree_size : ins.tree_size + ins.n] = init_arr[:]
        # 下から上に向かって演算結果を埋めていく
        # i << 1 は左の子(2i)、i << 1 | 1 は右の子(2i+1)
        for i in range(ins.tree_size - 1, 0, -1):
            ins.tree[i] = fold_op(ins.tree[i << 1], ins.tree[i << 1 | 1])
        return ins

    def update(self, i: int, x) -> None:
        """ i番目の要素をxに更新し、関連する親ノードを再計算する / O(log N) """
        # 指定されたインデックスを木の中の葉の位置に変換
        i += self.tree_size
        self.tree[i] = x
        # 根に到達するまで（i > 1の間）親へ登りながら更新
        while i > 1:
            i >>= 1 # 親のインデックスへ移動 (i // 2)
            # 常に左右の子を再計算して親の値を更新
            self.tree[i] = self.fold_op(self.tree[i << 1], self.tree[i << 1 | 1])

    def fold_range(self, l: int, r: int):
        """ 半開区間 [l, r) に対して演算（クエリ）を行う / O(log N) """
        res_l = res_r = self.tree[0] # 単位元で初期化（__init__でe_foldがtree[0]にある前提）
        l += self.tree_size
        r += self.tree_size

        while l < r:
            # lが右の子（奇数）なら、そのノードを計算に含めて右隣の親の範囲へ移動
            if l & 1:
                res_l = self.fold_op(res_l, self.tree[l])
                l += 1
            # rが右の子（奇数）なら、その左隣（左の子）を計算に含める
            if r & 1:
                r -= 1
                res_r = self.fold_op(self.tree[r], res_r)
            
            # 親の階層へ移動
            l >>= 1
            r >>= 1
        return self.fold_op(res_l, res_r)

    def __getitem__(self, i: int):
        """ st[i] で葉の値を取得 """
        return self.tree[self.tree_size + i]

    def __setitem__(self, i: int, item) -> None:
        """ st[i] = x で値を更新 """
        self.update(i, item)

    def __iter__(self):
        """ 葉の要素を順番に回すイテレータ """
        yield from self.tree[self.tree_size : self.tree_size + self.n]

    def __str__(self) -> str:
        return f"{self.__class__.__name__}({list(self)})"


A = [3, 1, 4, 1, 5, 9, 2, 6, 5]
# インスタンス生成（配列を引数にする）
st = SegmentTree.from_array(A, max, float("-inf"))

st.update(6, 100)
# [3, 1, 4, 1, 5, 9, [100], 6, 5]

# 区間積の計算
print(st.fold_range(2, 9))  # 100
# [3, 1, [ 4, 1, 5, 9, 100, 6, 5)]

派生

動的木による実装

通常のセグメント木のように「最初に全ての配列サイズを確保する」のではなく、「必要なノードだけを、必要な時に（オンデマンドで）作成する」実装。これにより、例えばインデックスが 0 から 10⁹（10億）まであるような非常に広い範囲でも、実際に更新・参照する箇所が少なければ、メモリを節約して扱うことができる。^[12]

遅延評価セグメント木

通常のセグメント木の機能に加えて、区間に対する作用（区間加算や区間更新など）を実行できるデータ構造。作用の情報を別の木で持ち、参照時に必要箇所だけ反映させることで、区間に対する作用を高速化している。^[13]

双対セグメント木

「要素一つの更新・区間の積」ができる通常のセグメント木とは逆に、「区間に対する作用・要素一つの取得」を実行できるデータ構造。^[14]

永続セグメント木

永続データ構造として構成されたセグメント木。ある時点における区間積などを提供できる。^[15]