セグメントツリー（Segment Tree）とは？データ構造の基本と仕組みをわかりやすく解説

セグメントツリーとは

セグメントツリー（Segment Tree）は、配列に対する「区間に関する問い合わせ」と「要素の更新」を高速に処理するためのデータ構造です。本記事では、セグメントツリーが必要とされる背景と、その基本的な構成方法について解説します。

解決したい問題

まず、次のような問題を考えてみましょう。長さ n の配列 arr[0 … n-1] が与えられたとき、以下の2つの操作を効率よく行いたいとします。

• 区間和の取得：インデックス l から r までの要素の合計を求める（0 ≤ l ≤ r ≤ n-1）
• 要素の更新：指定したインデックス i の値を新しい値 x に変更する（arr[i] = x、i は 0 ～ n-1 の範囲）

素朴なアプローチの課題

単純な実装では、区間和を求めるたびに l から r までを順番に足し算するため、1回のクエリに O(n) の時間がかかります。一方、あらかじめ累積和を計算しておけば区間和は O(1) で求められますが、要素を更新するたびに累積和を作り直す必要があり、今度は更新操作に O(n) かかってしまいます。

このように、どちらか一方だけを高速化すると、もう一方が遅くなるというトレードオフが生じます。両方の操作をバランスよく高速にこなせるのがセグメントツリーです。

セグメントツリーの構造

セグメントツリーを利用すると、区間和の取得も要素の更新も、どちらも O(log n) の時間で処理できます。ツリーは次のように表現されます。

• 葉ノード：元の配列の各要素に対応します
• 内部ノード：子ノード（部分区間）の情報を統合した結果を保持します。統合方法（マージ処理）は扱う問題によって異なりますが、今回は「そのノードの下にあるすべての葉の合計」を表します

具体例：配列 [1, 3, 5, 7, 9, 11]

例として、配列 [1, 3, 5, 7, 9, 11] からセグメントツリーを構築してみましょう。

根ノードには配列全体の合計である 36 が格納されます。その下には、前半区間 [1, 3, 5] の合計 9 と、後半区間 [7, 9, 11] の合計 27 を持つ2つの子ノードがぶら下がります。さらに各区間を半分ずつに分割していくと、最終的に葉ノードには元の配列の要素 1, 3, 5, 7, 9, 11 が並びます。

計算量のまとめ

• ツリーの構築：O(n)
• 区間和クエリ：O(log n)
• 要素の更新：O(log n)

この特性により、セグメントツリーは競技プログラミングや大規模データに対する範囲集計処理など、更新と参照が頻繁に行われる場面で広く活用されています。また、マージ処理を「合計」から「最小値」「最大値」「GCD」などに置き換えることで、さまざまな種類の区間クエリにも対応可能です。