セグメント木

ウィキペディア

セグメント木

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/02/06 00:01 UTC 版)

セグメント木
種類	二分木
発表時期	1977
発明者	ジョン・ベントリー
ビッグオー記法による計算量 (en)
アルゴリズム 平均 最悪の場合 空間 O(n) O(n) 探索 O(logn) O(logn) 挿入 O(logn) O(logn)

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

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

セグメント木の構造の図解例。下部に示されたセグメントに対して構築されている。

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

$(-\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 )$

要素として整数、演算として和のモノイドを載せたセグメント木の構造の図解例。配列の区間和（薄墨の部分）を得たい場合、あらかじめ計算した区間に対応するノード（薄墨の9, 17）だけを足せばいい。

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

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

クエリの種類	演算内容 (⋅)	単位元 (e)	備考
範囲合計 (RSQ)	加算 (+)	0	-
範囲最小値 (RMQ)	$\min(a,b)$	この節の加筆が望まれています。 （2007年11月）

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

引用文献

• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2000). “More Geometric Data Structures”. Computational Geometry: algorithms and applications (2nd ed.). Springer-Verlag Berlin Heidelberg New York. doi:10.1007/978-3-540-77974-2. ISBN 3-540-65620-0. https://archive.org/details/computationalgeo00berg 
• Stabbing Problem

外部リンク

• Segment Tree - Algorithms for Competitive Programming