セグメント木

セグメント木（せぐめんとき、）や区分木（くぶんぎ）は、計算機科学において、区間や線分に関する情報を格納するために用いられるデータ構造である。似たデータ構造に区間木がある。

n個の区間の集合 に対するセグメント木は、O(n log n) の記憶領域を使用し、 の時間で構築できる。セグメント木は、線分の集合が与えられたとき、特定の点を含むすべての線分を の時間で探索するスタビングクエリ（stabbing query）を解決することが主な目的となる（ここで k は取り出された線分の数）。

セグメント木は、計算幾何学、地理情報システム、機械学習など、広範な分野で活用される。さらに、高次の次元に一般化することができる。

セグメント木という名称は、大きく2つの用途で用いられる。計算幾何学の教科書では、区間（線分）の集合に対するスタビングクエリのための構造を指す。一方、競技プログラミングなどでは、モノイドの要素を並べた配列に対して、一点更新と区間積の計算を対数時間で行う構造を指すことが多い。本記事では前半で前者を、#モノイドに対するセグメント木の構成以降で後者を扱う。

定義

以下では、線分の集合が与えられたとき、特定の点を含むすべての線分を の時間で探索するスタビングクエリ（stabbing query）に回答するセグメント木について説明する。

モノイドを用いたセグメント木については#モノイドに対するセグメント木の構成を参照。

説明

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

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

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

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

構築

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

Int(T) が X に含まれるなら、X を T に格納して終了する。 そうでない場合： X が T の左の子の区間と交差するなら、再帰的に X をその子に挿入する。 X が T の右の子の区間と交差するなら、再帰的に X をその子に挿入する。 構築操作全体には の時間がかかる。ここで n は に含まれるセグメントの数である。

クエリ

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

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

に含まれるすべての区間を報告する。

v が葉でない場合：

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

n個の区間を含むセグメント木において、与えられたクエリ点を含む区間は の時間で報告できる。ここで k は報告された区間の数である。

記憶領域の要件

n個の区間の集合 に対するセグメント木 T は、 の記憶領域を使用する。

集合 には最大 4n + 1 個の基本区間がある。T は最大 4n + 1 個の葉を持つ平衡二分木であるため、その高さは である。任意の区間が木の特定の深さで格納されるのは最大2回までであるため、記憶領域の総量は となる。

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

を用いることで、クエリ時間の境界を対数係数分だけ下げることができる。関連する構造の最も深いレベルで区間木を用いることで、記憶領域の境界を対数係数分だけ下げることができる。

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

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

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

つまり、集合を配列のような順序のあるデータ構造で持つとすると、以下の操作を時間計算量 で行うことができる。 番目の要素にを代入 番目の要素を取得 番目の要素から番目の要素のモノイド積を計算

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

配列ベースの実装と構造 効率的なライブラリ実装のため、ポインタを用いた木構造の代わりに、連続したメモリ領域（配列）を用いた「ヒープのような管理」が行われることもある。 この手法は、キャッシュの局所性が高く、実装がポインタを用いた木構造よりも簡潔になるという利点がある。

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

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

左の子ノード: （i << 1） 右の子ノード: （i << 1 | 1） 親ノード: （整数除算）（i >> 1）

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

+ 要素の位置関係（括弧内は木におけるインデックス）親 (1)i >> 1 自分 (2)i (3)i ^ 1 子 (4)i << 1 (5)i << 1 | 1 (6) (7) 配列 (8)x0 (9)x1 (10)x2 (11)x3 (12)x4 (13)x5 (14)x6 (15)x7

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

葉ノードの数: （n 以上で最小の2の冪数） 内部ノードの数: 合計ノード数:

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

基本操作の詳細アルゴリズム セグメント木の主要な操作は「構築」、「一点更新」、「範囲クエリ」の三つである。これらの操作はすべて、木の高さ に依存する計算量を持つ。

構築 構築操作は、与えられた初期配列からセグメント木を生成するプロセスである。計算量は 。

単位元で配列を確保する。 配列の要素を木の葉ノード（インデックス N から N+n−1）に配置する。 下の階層から順に、隣接する二つの子ノードの値をマージしてモノイド積の値を決定していく。 このプロセスを根ノード（インデックス1）に達するまで繰り返す。

一見すると各ノードに対して操作を行うためかかるように思われるが、各階層のノード数は上に行くほど半分になるため、幾何級数の和としてで収束する。

例として初期配列A = [3, 1, 4, 1, 5, 9, 2, 6, 5]に基づき構築することを考える（要素は整数、モノイド積はmax）。 まず配列の要素を葉ノードに配置する。葉ノード以外は単位元である-∞が配置されていることに注意。

+ 構築（括弧内は木におけるインデックス）根 (1)-∞ - (2)-∞ (3)-∞ - (4)-∞ (5)-∞ (6)-∞ (7)-∞ - (8)-∞ (9)-∞ (10)-∞ (11)-∞ (12)-∞ (13)-∞ (14)-∞ (15)-∞ 葉（配列） (16)3 (17)1 (18)4 (19)1 (20)5 (21)9 (22)2 (23)6 (24)5 (25)-∞ (26)-∞ (27)-∞ (28)-∞ (29)-∞ (30)-∞ (31)-∞

次に下の階層（インデックスだと15）から上に向かって、隣接する二つの子ノードの値をモノイド積して親ノードの値を決定していく。 例えばインデックス10において、子ノードはそれぞれ20（2×10）, 21（2×10+1）なので、子ノードの値5, 9を用いてインデックス10はと計算される。

+根 (1)9 - (2)9 (3)5 - (4)4 (5)9 (6)5 (7)-∞ - (8)3 (9)4 (10)9 (11)6 (12)5 (13)-∞ (14)-∞ (15)-∞ 葉（配列） (16)3 (17)1 (18)4 (19)1(20)5(21)9 (22)2 (23)6 (24)5 (25)-∞ (26)-∞ (27)-∞ (28)-∞ (29)-∞ (30)-∞ (31)-∞

これを根ノード（インデックス1）に達するまで繰り返せば、上図のようなセグメント木が構築できる。

一点更新 特定のインデックスiの値を変更し、その変更を木全体に反映させる操作である。計算量は。

対象となる葉ノードの値を更新する。 その後、そのノードの親、さらにその親へと、根に向かって値を再計算しながら遡っていく。

各ステップでは、自分の兄弟ノードの値と自分の新しい値とのモノイド積を計算するだけで済むため、各階層で定数時間の操作となり、全体で となる。 ただしモノイド積の計算量が大きい場合（例えば行列積）、その計算量も考慮する必要がある。

下図においてインデックス22を100に置き換えることを考える。 まず対象となるインデックス22を100に更新する。次に更新によって親ノードを再計算する必要があるので、インデックス22の兄弟ノードを特定する必要がある。あるノード i の兄弟ノードは、そのノードが左右どちらのノードであるかにかかわらず i ^ 1のビット演算（^はビット排他的論理和）で導出できる。この計算によりインデックス22の兄弟ノードはインデックス23と導出できるので、それぞれの値を元に親ノードを再計算する（親ノードのインデックスは i >> 1で導出できる）。 親ノードが変化すると、親ノードの親ノードを再計算しなければならないので、上記と同様の方法で親ノードの兄弟ノードを特定し、親ノードの親ノードを再計算する。 これを根に達するまで再計算しながら遡っていけばいい。

+ 更新（濃い赤が更新対象、薄い赤はその兄弟ノード）根 (1)100 - (2)100 (3)5 - (4)4 (5)100 (6)5 (7)-∞ - (8)3 (9)4 (10)9 (11)100 (12)5 (13)-∞ (14)-∞ (15)-∞ 葉（配列） (16)3 (17)1 (18)4 (19)1 (20)5 (21)9 (22)100 (23)6 (24)5 (25)-∞ (26)-∞ (27)-∞ (28)-∞ (29)-∞ (30)-∞ (31)-∞

範囲クエリ 指定された区間の要素をすべてモノイド積でかけ合わせた値を導出する。計算量は。 セグメント木の各ノードは、特定の区間のモノイド積（和、最大値、最小値など）を保持している。「親」に行くほど広い範囲の計算結果を持っている。 クエリの範囲の両端に対応する葉から探索を開始し、クエリの範囲に含まれるノードを上に向かって拾い集めることで計算する。

探索ノードをそれぞれクエリの範囲の両端にNを足した値で初期化する。 探索ノードが拾う結果を単位元で初期化する。 （左端と右端がぶつかる）となるまで、以下を繰り返す。 （l が奇数）のとき、そのノードは右の子ノード、つまり「親がカバーする範囲の右側」にいる。この場合、親ノードに登ってしまうと、範囲外（左側）のデータまで含んでしまう。なので今いるノードの値を確定させて（ にかけて）、右隣のブロックへ移動 () する。 （r が奇数）のとき、は偶数（クエリのrは半開区間であることに注意）なので、そのノードは左の子ノード、つまり「親がカバーする範囲の左側」にいる。この場合左端の時と同様、親ノードに登ってしまうと、範囲外（右側）のデータまで含んでしまう。なのでのノードの値を確定させる（ にかけて）。 上に登る（） 得られた二つの結果のモノイド積を計算して返す。

このアルゴリズムにおいて、各階層で結果に「一部含まれる」と判定されるノードは常に高々2個であるため、訪問するノードの総数は 程度に抑えられ、計算量は に保たれる 。

範囲クエリとしてが与えられたとする（インデックス2以上9未満の配列要素の最大値を求めたい）。il=2+16=18, ir=9+16=25となり、それぞれ順番に計算すると、 ループ1 il=18は偶数なので、計算しない ir=25は奇数なので、 ir=25-1=24と更新 resr=max(5, resr)=max(5, -∞)=（resl, resrは単位元-∞で初期化されていることに注意） il, irを÷2（整数除算）し il=9, ir=12と更新 ループ2 il=9は奇数なので、 resl=max(resl, 4)=max(-∞, 4)= il=9+1=10と更新 ir=12は偶数なので、計算しない il, irを/2（整数除算）しil=5, ir=6と更新 ループ3 il=5は奇数なので、 resl=max(resl, 100)=max(4, 100)= il=5+1=6と更新 ir=6は偶数なので、計算しない il, irを/2（整数除算）しil=3, ir=3と更新 ループ4 il < ir を満たさなくなったのでループ終了 max(resl, resr)=max(100, 5)=100を返す

+ 範囲クエリ（濃い部分が計算に利用されるノード）根 (1)100 - (2)100 (3)5 - (4)4 (5)100 (6)5 (7)-∞ - (8)3 (9)4 (10)9 (11)100 (12)5 (13)-∞ (14)-∞ (15)-∞ 葉（配列） (16)3 (17)1 (18)4 (19)1 (20)5 (21)9 (22)100 (23)6 (24)5 (25)-∞ (26)-∞ (27)-∞ (28)-∞ (29)-∞ (30)-∞ (31)-∞

実装例 Pythonによる実装例を示す。ここでは上述の配列ベースの非再帰実装を用いており、再帰による実装に比べて関数呼び出しのオーバーヘッドが小さい。なお、区間への作用（区間加算など）が必要な場合は、遅延評価セグメント木を用いる。 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 # 単位元で初期化（__init__でe_foldがtreeにある前提） 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, , 6, 5]

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

備考 セグメント木は、記憶領域の要件が区間木の に対して と多いため、1次元の範囲クエリにおいては区間木よりも効率が悪い。セグメント木の重要性は、各ノードの正準サブセット内の線分を、任意の方法で格納できる点にある。

端点が小さな整数の範囲（例：[1, ..., O(n)] の範囲）にあるn個の区間については、線形な前処理時間と、与えられたクエリ点を含むすべてのk個の区間を報告するためのクエリ時間 を持つ最適なデータ構造が存在する。

セグメント木のもう一つの利点は、カウントクエリ（与えられた点を含む線分自体を報告するのではなく、その数を報告するクエリ）に容易に適応できることである。正準サブセットに区間を格納する代わりに、単にその数を格納すればよい。このようなセグメント木は線形の記憶領域を使用し、 のクエリ時間を必要とするため、最適である。

区間木やの高次元版は存在しない。つまり、高次元で同様の問題を解決する、これらの構造の明確な拡張は存在しない。しかし、これらの構造はセグメント木の関連構造として利用できる。

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

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

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

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

他のデータ構造との比較 配列に対する区間クエリには、セグメント木以外にもフェニック木（Binary Indexed Tree、BIT）やスパーステーブルといった構造が用いられる。以下に主な違いを示す。ここで n は要素数である。

+ 配列に対する区間クエリ用データ構造の比較 データ構造 構築 一点更新 区間クエリ 備考 セグメント木 結合法則を満たす演算（モノイド）なら任意に扱える フェニック木 区間和は2つの累積和の差で求めるため、逆元を持つ演算が前提となる。実装は短い スパーステーブル 更新不可 最小値のように重複して適用しても結果が変わらない演算に限られる

更新を伴わず最小値などを繰り返し求めるだけであればスパーステーブルが、和のように逆元を持つ演算で一点更新と区間和だけが必要であればフェニック木が、それぞれ候補となる。一方、最小値・最大値のように逆元を持たない演算に更新を組み合わせる場合や、区間への作用が必要な場合には、セグメント木が選ばれる。

応用 計算幾何学 区間や線分の集合に対するスタビングクエリのほか、長方形の集合の和集合の面積を求める問題（クレーの測度問題の2次元版）に用いられる。これはセグメント木の発明の契機となった問題でもある。

範囲クエリ 配列に対する区間和、区間最小値・最大値、区間の最大公約数・最小公倍数などの計算に用いられる。これらはいずれもモノイドの演算として表せる。さらに、配列の接頭辞のうち和が指定値に達する最短のものの探索や、k 番目に現れる0の探索といった、木の上での二分探索を伴う問題にも拡張できる。

区間更新・履歴の保持 遅延評価セグメント木を用いると、区間加算や区間代入を対数時間で処理できる。また、永続セグメント木は、配列の区間内の k 番目に小さい値を求める問題などに応用される。

歴史 セグメント木は、1977年にによって（n個の長方形の集合が与えられたとき、それらの和集合の面積を求める問題）の中で発明された。

クレーの測度問題は、同年にヴィクター・クリーが、実数直線上の n 個の区間の和集合の長さを より少ない手間で求められるかという形で提起した問題である。ベントリーはその2次元版である長方形の和集合の面積を、同じ の時間で求めるアルゴリズムを示した。

脚注

注釈

出典

引用文献

Stabbing Problem

外部リンク Segment Tree - Algorithms for Competitive Programming