セグメント木

セグメント木
種類	二分木
発表時期	1977
発明者	ジョン・ベントリー（英語版）
ビッグオー記法による計算量 (en)

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

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

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

定義

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

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

説明

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

つまり、基本区間のリストは、隣接する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 をその子に挿入する。

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

証明 —

端点のソートには

O\left(n\log n\right)

かかる。ソートされた端点から平衡二分木を構築するのには、n に対して線形時間がかかる。

区間 X = [x, x′] の木への挿入コストは

O\left(\log n\right)

である。

証明 — 各ノードの訪問には一定時間がかかる（正準サブセットが連結リストのような単純なデータ構造に格納されていると仮定）。ノード v を訪問するとき、X を v に格納するか、あるいは Int(v) が X の端点を含んでいるかのどちらかである。上述のように、ある区間が木の各レベルで格納されるのは最大2回までである。また、各レベルにおいて、対応する区間が x を含むノードは最大1つであり、x′ を含むノードも最大1つである。したがって、各レベルで訪問されるノードは最大4つである。レベル数は $O\left(\log n\right)$ であるため、挿入の総コストは $O\left(\log n\right)$ となる。^[2]

クエリ

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

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

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

v が葉でない場合：

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

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

証明 — クエリアルゴリズムは木の各レベルで1つのノードを訪問するため、合計で $O\left(\log n\right)$ 個のノードを訪問する。一方で、あるノード v において、 $I$ 内のセグメントは $O\left(1+k_{v}\right)$ の時間で報告される。ここで k_v は、訪問されたノード v で報告された区間の数である。訪問されたすべてのノード v における k_v の総和は、報告されたセグメントの数 k となる。^[6]

記憶領域の要件

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

補題 ― $I$ の任意の区間 [x, x′] が、同じ深さのノードの正準集合に格納されるのは最大2回までである。

証明 — 同じ深さにある3つのノードを左から順に v₁, v₂, v₃ とし、任意のノード v の親ノードを p(v) とする。[x, x′] が v₁ と v₃ に格納されていると仮定する。これは、[x, x′] が Int(v₁) の左端点から Int(v₃) の右端点までの全区間にわたっていることを意味する。特定のレベルにおけるすべてのセグメントは重複せず、左から右に並んでいることに注意せよ。これは葉を含むレベルについては構築上真であり、隣接するセグメントのペアを結合して上のレベルに移動しても、この特性は失われない。さて、parent(v₂) = parent(v₁) であるか、あるいは前者が後者の右側にある（木のエッジは交差しない）。前者の場合、Int(parent(v₂)) の左端点は Int(v₁) の左端点と同じである。後者の場合、Int(parent(v₂)) の左端点は Int(parent(v₁)) の右端点の右側にあり、したがって Int(v₁) の右端点の右側にある。いずれの場合も、Int(parent(v₂)) は Int(v₁) の左端点、またはその右側から始まる。同様の理由で、Int(parent(v₂)) は Int(v₃) の右端点、またはその左側で終わる。したがって、Int(parent(v₂)) は [x, x′] に含まれなければならない。ゆえに、[x, x′] は v₂ には格納されない。

集合

I

には最大 4n + 1 個の基本区間がある。T は最大 4n + 1 個の葉を持つ平衡二分木であるため、その高さは

O\left(\log n\right)

である。任意の区間が木の特定の深さで格納されるのは最大2回までであるため、記憶領域の総量は

O\left(n\log n\right)

となる。^[6]

高次元への一般化

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

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

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

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

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

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

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

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

配列ベースの実装と構造

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

完全二分木による表現

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

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

左の子ノード: $2i$ （i << 1）
右の子ノード: $2i+1$ （i << 1 | 1）
親ノード: $i/2$ （整数除算）（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) x₀	(9) x₁	(10) x₂	(11) x₃	(12) x₄	(13) x₅	(14) x₆	(15) x₇

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

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

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

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

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

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

構築

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

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

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

例として初期配列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は $\max(5,9)=9$ と計算される。


根	(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の値を変更し、その変更を木全体に反映させる操作である。計算量は $O\left(\log n\right)$ 。

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

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

下図においてインデックス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) -∞

範囲クエリ

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

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

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

範囲クエリとして $[2,9)$ が与えられたとする（インデックス2以上9未満の配列要素の最大値を求めたい）。i_l=2+16=18, i_r=9+16=25となり、それぞれ順番に計算すると、

ループ1
1. i_l=18は偶数なので、計算しない
2. i_r=25は奇数なので、
  1. i_r=25-1=24と更新
  2. res_r=max(5, res_r)=max(5, -∞)=5と更新
    （res_l, res_rは単位元-∞で初期化されていることに注意）
3. i_l, i_rを÷2（整数除算）し i_l=9, i_r=12と更新
ループ2
1. i_l=9は奇数なので、
  1. res_l=max(res_l, 4)=max(-∞, 4)=4と更新
  2. i_l=9+1=10と更新
2. i_r=12は偶数なので、計算しない
3. i_l, i_rを/2（整数除算）しi_l=5, i_r=6と更新
ループ3
1. i_l=5は奇数なので、
  1. res_l=max(res_l, 100)=max(4, 100)=100と更新
  2. i_l=5+1=6と更新
2. i_r=6は偶数なので、計算しない
3. i_l, i_rを/2（整数除算）しi_l=3, i_r=3と更新
ループ4
1. i_l < i_r を満たさなくなったのでループ修了
max(res_l, res_r)=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[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)]

備考

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

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

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

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

派生

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

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

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

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

歴史

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

脚注

[脚注の使い方]

注釈

↑ 2N-1 = 2・2^k+1-1 = 4・2^k-1+4-4 = 4(2^k+1)-5 = 4n-5
↑ 例えばn=9（2³+1）のとき、N=16（2³⁺¹）となり、内部ノード数は15、合計ノード数は16+15=31となる。

出典

1 2 3 (de Berg et al. 2000, p. 229)
1 2 (de Berg et al. 2000, p. 227)
↑ (de Berg et al. 2000, p. 224)
↑ (de Berg et al. 2000, pp. 225–226)
↑ (de Berg et al. 2000, pp. 226–227)
1 2 (de Berg et al. 2000, p. 226)
1 2 (de Berg et al. 2000, p. 230)
↑ “セグメント木を使う”. Zenn (2022年5月14日). 2026年1月8日閲覧。
↑ “Segment Trees”. hackerearth.com. 2026年1月8日閲覧。
↑ “非再帰セグ木サイコー！一番すきなセグ木です”. hcpc-hokudai.github.io (2019年11月21日). 2026年1月8日閲覧。
↑ (de Berg et al. 2000, pp. 229–230)
↑ “Range Sum Query (動的セグメント木)”. tjkendev.github.io. 2026年1月8日閲覧。
↑ “遅延評価セグメント木をソラで書きたいあなたに”. tsutaj.hatenablog.com (2017年3月30日). 2026年1月8日閲覧。
↑ “双対セグメント木という概念について”. kmyk.github.io (2019年2月22日). 2026年1月8日閲覧。
↑ “pythonで永続セグメント木実装”. qiita.com (2021年10月3日). 2026年1月8日閲覧。

引用文献

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
Stabbing Problem

外部リンク

Segment Tree - Algorithms for Competitive Programming

[10] 2N-1 = 2・2^k+1-1 = 4・2^k-1+4-4 = 4(2^k+1)-5 = 4n-5

[11] 例えばn=9（2³+1）のとき、N=16（2³⁺¹）となり、内部ノード数は15、合計ノード数は16+15=31となる。

[Schwarzkopf4-1] 1 2 3 (de Berg et al. 2000, p. 229)

[Schwarzkopf1-2] 1 2 (de Berg et al. 2000, p. 227)

[3] (de Berg et al. 2000, p. 224)

[4] (de Berg et al. 2000, pp. 225–226)

[5] (de Berg et al. 2000, pp. 226–227)

[Schwarzkopf2-6] 1 2 (de Berg et al. 2000, p. 226)

[Schwarzkopf3-7] 1 2 (de Berg et al. 2000, p. 230)

[8] “セグメント木を使う”. Zenn (2022年5月14日). 2026年1月8日閲覧。

[9] “Segment Trees”. hackerearth.com. 2026年1月8日閲覧。

[12] “非再帰セグ木サイコー！一番すきなセグ木です”. hcpc-hokudai.github.io (2019年11月21日). 2026年1月8日閲覧。

[13] (de Berg et al. 2000, pp. 229–230)

[14] “Range Sum Query (動的セグメント木)”. tjkendev.github.io. 2026年1月8日閲覧。

[15] “遅延評価セグメント木をソラで書きたいあなたに”. tsutaj.hatenablog.com (2017年3月30日). 2026年1月8日閲覧。

[16] “双対セグメント木という概念について”. kmyk.github.io (2019年2月22日). 2026年1月8日閲覧。

[17] “pythonで永続セグメント木実装”. qiita.com (2021年10月3日). 2026年1月8日閲覧。

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[注 1]

[注 2]

[10]

[11]

[12]

[13]

[14]

[15]

表話編歴木構造 (計算機科学)
二分木	二分探索木（BST） Cartesian tree Top tree T tree
平衡2分探索木	AA木 AVL木赤黒木 Scapegoat tree スプレー木 Treap
B木	B+木 B*木 B^x-tree UB-tree 2-3木 2-3 フィンガーツリー 2-3-4木 (a,b)-tree Dancing tree Htree
トライ木	基数木接尾辞木接尾辞配列三分探索木二分トライ木 x-高速トライ木 y-高速トライ木
バイナリ空間分割木(BSP木)	四分木八分木 k-d 木 Implicit k-d tree vp-tree
非二分木	Exponential tree Fusion tree 区間木 PQ tree Range tree SPQR tree Van Emde Boas tree
空間データパーティショニング木	R木 R+ tree R* tree X-tree M-tree セグメント木 Hilbert R-tree Priority R-tree
ヒープ	二分ヒープ二項ヒープフィボナッチヒープ 2-3 heap Beap D-ary heap Leftist heap Pairing heap Skew heap Soft heap Ternary heap
その他の木構造	Hash tree Finger tree Metric tree Cover tree BK-tree Doubly-chained tree iDistance Link-cut tree フェニック木
カテゴリ