セグメント木・とは？初心者にもわかる徹底解説共起語・同意語・対義語も併せて解説！

この記事を書いた人

高岡智則

年齢：33歳性別：男性職業：Webディレクター（兼ライティング・SNS運用担当）居住地：東京都杉並区・永福町の1LDKマンション出身地：神奈川県川崎市身長：176cm 体系：細身〜普通（最近ちょっとお腹が気になる）血液型：A型誕生日：1992年11月20日最終学歴：明治大学・情報コミュニケーション学部卒通勤：京王井の頭線で渋谷まで（通勤20分）家族構成：一人暮らし、実家には両親と2歳下の妹恋愛事情：独身。彼女は2年いない（本人は「忙しいだけ」と言い張る）

セグメント木とは何か

セグメント木・とは大きな配列の区間情報を効率的に管理するデータ構造の一つです。日常の例で言えば、長い1次元の数列の中から「ある区間に含まれる数の総和を知りたい」というような問題を、すばやく答えるために使います。

木構造を使う点が特徴で、根は全体の区間を、葉は配列の各要素を表します。各ノードにはその区間の情報が格納され、子ノードの情報を組み合わせて親ノードの値を作っています。

セグメント木の強さは次の2点に集約されます。1つは区間を分割して扱える柔軟さ、2つ目は区間の情報を素早く集計できる点です。

どうやって作るのか

作り方はシンプルな再帰の考え方で、配列の区間を半分ずつ分割していきます。あるノードが表す区間を [l, r] とすると、中央を m = (l + r) / 2 とし、左の子は [l, m]、右の子は [m+1, r] を担当します。これを葉まで進めると、葉ノードは元の配列の各要素に対応します。

各ノードにはどんな値を入れるのかのは使い方次第です。和をとりたいなら「区間内の和」、最大値を知りたいなら「区間内の最大値」など、用途に合わせて値を決めます。内部ノードは左の子と右の子の値を組み合わせて作ります。例えば和の場合は左 + 右、最大値の場合は左と右の最大値の大きい方を取ります。

具体的な例を考えよう

長さ4の配列を例にとります。配列を [2, 1, 5, 3] とすると、葉ノードはそれぞれ 2, 1, 5, 3 を表します。根は区間全体 [0, 3] を表し、左の子は [0, 1]、右の子は [2, 3] を担当します。さらに左の子は [0, 0] と [1, 1]、右の子は [2, 2] と [3, 3] のように分かれていきます。このとき和を取るセグメント木なら、根の値は 2+1+5+3 = 11 となります。左の子の値は 2+1 = 3、右の子の値は 5+3 = 8 となります。部分的な区間の和を知りたい場合は、該当するノードだけをたどって結果を得ることができます。

クエリの仕組み

区間の和や最大値などの「クエリ」を実行する場合、木を辿って目的の区間に対応するノードを集めます。すべてのクエリは O(log n) の時間で処理でき、長い配列でも高速です。実際には、左右の子を比較しながら、必要な範囲だけを走査します。もしクエリが [l, r] のような連続区間であれば、途中で不要な部分を切り捨て、効率的に結果を得ることができます。

更新の仕組み

配列のある要素を変更したい場合も、セグメント木は素早く対応します。変更は葉ノードの値を新しい値に置き換え、親ノードを遡って再計算します。これを繰り返すことで、木全体の情報が一貫した状態になります。更新のコストも O(log n) です。

実装のポイントと使い方のヒント

よく使われるのは「区間の和」「区間の最小値・最大値」「区間の最小公倍数のような複雑な関数」などです。実装上のポイントとしては、配列サイズを 4n 程度用意することで再帰的ビルドを安定させること、葉ノードと内部ノードの関係を明確に保つこと、更新とクエリの両方を同じ再帰的な考え方で実装することです。具体的には、ビルド関数・クエリ関数・更新関数の3つを作り、それぞれが [l, r] の区間を管理する形にします。コードを見やすくするためには、区間を表す変数を明確に命名し、左・右の子を左右のインデックスとして参照することが重要です。

よくある使い方の表

用途	例	説明
区間和	任意の [l, r] の和	区間内の全要素の和を求める
区間最大値	最大値を求める	区間内の最大の値を取得

まとめ

セグメント木は大きな配列の区間情報を効率的に扱える強力なデータ構造です。葉ノードは元の要素を、内部ノードは子ノードの情報を組み合わせて全体の情報を保ちます。クエリと更新の両方を O(log n) で実行できる点が魅力で、競技プログラミングやデータ分析の現場でも広く使われています。初心者はまず「木のイメージ」と「区間の和を例にとる」学習から始め、徐々に他の演算へ拡張していくと理解が深まります。

セグメント木の同意語

セグメント木: 配列の連続区間を管理し、区間の和・最小値・最大値などのクエリと区間の更新を高速に処理できるデータ構造。
セグメントツリー: セグメント木の別表記。区間情報を木状に組織化して、区間クエリの計算を対数時間で行えるデータ構造。
区間木: 日本語表現の一般名。連続区間を扱い、クエリと更新を効率的に処理するデータ構造。
区間木構造: 区間を管理する木構造という意味の表現。セグメント木と同義で使われることがある用語。
区間木データ構造: 区間を扱うデータの構造全般を指す言い方で、セグメント木と同じ役割を持つデータ構造。

セグメント木の対義語・反対語

全走査: セグメント木のようなデータ構造を使わず、区間の和や最小値を区間内の全要素を順に調べて計算する方法。計算量は O(n) で、大きなデータには不向き。
ナイーブ法: 前処理をほとんど行わず、区間ごとにその場で計算する古典的手法。実用上は低速化しやすい。
ブルートフォース: 入力全体を直接走査して答えを出す最も素朴な方法。セグメント木と比べてパフォーマンスが劣ることが多い。
直接配列参照: 木構造を使わず、元の配列を直接参照して計算するアプローチ。動的更新には向かないことが多い。
線形走査: データを線形に1つずつ検査して結果を得る方法。区間クエリが多いと処理時間が長くなる。
配列ベースの計算: データを配列として直接扱い、区間情報を木構造無しで計算する手法。更新頻度が高いと不利。
静的データ構造: データがほぼ変更されない前提の構造。動的更新対応のセグメント木と比べて柔軟性が低い場合が多い。
全域前提の計算: 区間情報を前処理せず、全体情報だけで計算を完結させる発想。局所的な区間情報を活かせない点が対比になる。

セグメント木の共起語

区間木: セグメント木の別称。連続する区間を木状に分割して管理するデータ構造です。
セグメントツリー: セグメント木の別表現。英語の segment tree の日本語表記で、同じ意味です。
区間和: ある区間のデータの総和を求めるクエリ。セグメント木でよく扱われる基本的な集約値のひとつです。
区間最小値: 区間内の最小値を求めるクエリ。
区間最大値: 区間内の最大値を求めるクエリ。
区間更新: 区間内の全要素を一括で変更する操作。遅延伝播と組み合わせて実装されることが多いです。
遅延伝播: 遅延させて反映する手法。更新をすぐ適用せず、必要になった時点で反映します。
ノード: セグメント木の要素。区間情報と子ノードへの参照を保持します。
葉ノード: 木の最下層のノード。元データの値を直接保持します。
親ノード: 子ノードの情報をまとめて保持する上位ノード。
子ノード: 下位のノード。
再帰: 区間を半分に分割して処理を進める再帰的な処理の仕方。
配列: 木を表現・格納する際に配列を用いる実装が一般的です。
木構造: 階層的なデータ構造の総称。セグメント木は木構造の一種です。
二分木: 各ノードが2つの子を持つ木。セグメント木は基本的に二分木として構成されます。
クエリ: 区間の情報を取得する操作。
更新: 区間の値を変更する操作。
構築: 初期データからセグメント木を作る過程。通常は葉から上へ集約して木を完成させます。
動的セグメント木: 必要に応じてノードを動的に生成する、データ量が変動する場面にも対応するセグメント木の変種です。
Fenwick木: 別名 BIT。区間和や点更新を高速に扱える別のデータ構造です。
BIT: Fenwick木の略称。
モノイド: 結合演算と単位元を用いて、汎用の集約関数を扱う理論的枠組み。セグメント木の設計に関係します。
結合関数: 子ノードの値を結合して親ノードの値を作る演算。和・最小値・最大値などが例です。
区間: 連続するデータの範囲。
範囲: 区間の別表現。文脈によって区間と同義で使われます。
計算量: アルゴリズムが要する時間・空間の指標。
O(log N): 操作の時間計算量を表す表記。セグメント木は通常これに近い性能を示します。
分割統治: Divide and Conquer の日本語表現。区間を分割して解を統合する考え方です。
マージ: 子ノードの値を結合して親ノードの値を作る処理。セグメント木の合成操作です。
初期化: 葉ノードにデータを設定し、上位へ値を伝えて木を完成させる作業。

セグメント木の関連用語

セグメント木: 区間のクエリと更新を高速に処理するデータ構造。木構造を用い、データを区間ごとに統合して管理する。通常は配列で実装される。
区間和: 指定した区間内の全要素の和を返すクエリ。セグメント木では各ノードが区間和を保持し、クエリをO(log n)で処理する。
区間最小値: 指定した区間内の最小値を返すクエリ。ノードは区間内の最小値を保持して結合する。
区間最大値: 指定した区間内の最大値を返すクエリ。ノードは区間内の最大値を保持して結合する。
区間積: 指定した区間内の全要素の積を返すクエリ。大きな値になる場合はモジュロを取る等の工夫が必要になることがある。
区間代入: 区間内の全要素を同じ値に置換する更新操作。遅延伝搬を用いて効率的に処理する。
区間加算: 区間内の全要素に一定の値を足す更新操作。遅延伝搬と組み合わせて効率化する。
遅延伝搬: 更新を先送りにして後で適用する技法。複数の更新を一括して適用でき、更新コストを削減する。
ノード: セグメント木の各木の節点。区間を表現し、データと結合結果を保持する。
リーフノード: 葉ノード。実データが格納される最下位のノードで、区間の最小単位を表す。
配列での実装: セグメント木を配列（通常はサイズ約2n）で表現する実装形式。
再帰的実装: 再帰関数を用いて区間を分割・統合する実装。分かりやすいがオーバーヘッドがあることがある。
非再帰的実装: ループとインデックス操作で実装する形式。高速でメモリ効率が良い場合が多い。
モノイド: セグメント木で扱う結合演算が満たすべき結合法則と単位元を指す概念。和・最小値・最大値・GCDなどが代表例。
結合演算: 2つの区間データを1つに結合する演算。和、最小値、最大値、GCDなどの演算が用いられる。
左子ノード: 現在のノードの左側の子ノードを指す。
右子ノード: 現在のノードの右側の子ノードを指す。
親ノード: 子ノードを統合して上位のノードを形成するノード。
木の高さ: セグメント木の深さ。通常はO(log n)程度で、nはデータ数。
0-index / 1-index: 配列のインデックスの基準。実装時に0-basedまたは1-basedを選択することがある。
2Dセグメント木: 2次元の区間クエリを扱う拡張。矩形領域の和・最小値などを扱える。
セグメント木 Beats: 区間更新のうち、特定の条件下で効率的に動作させる高度なテクニック。複雑な更新にも耐性を持つ場合がある。
Fenwick木: Binary Indexed Tree。点更新と区間和のクエリをO(log n)で処理する軽量な木構造だが、区間代入のような複雑な更新には不向き。