アルゴリズム - 12. セグメント木
セグメント木を使用するタイミング
セグメント木は、配列に対して範囲クエリと点更新を効率的に実行する必要がある場合に使用します。最も一般的には範囲合計クエリに使用されますが、以下のように応用できます：
- 範囲合計クエリ（古典的なユースケース）
- 範囲最小値/最大値クエリ（RMQ）
- 範囲GCD/LCMクエリ数学的演算用
- 条件を満たす要素の数範囲内で
- 範囲更新操作（遅延伝播を使用）
- 小さな範囲を組み合わせて計算できる任意の結合演算（XOR、AND、OR、乗算）
例題
リアルタイム取引ダッシュボード：100万銘柄 [s₀, s₁, ..., s₉₉₉,₉₉₉] を追跡し、数千人の同時ユーザーを持つライブ取引システムを構築しています。毎秒、システムは以下を処理する必要があります：
- 10,000以上の範囲クエリ：「234,567から456,789までの株式の合計値は？」
- 5,000以上の価格更新：「株式345,678の価格が$120から$125に変更されました」
- 両方が継続的かつ同時に発生
累積和配列が失敗する理由：
- 累積和配列はO(1)のクエリを提供しますが、各更新にO(n)が必要です
- n = 1,000,000で5,000回/秒の更新 = 50億操作/秒！💥
- システムは負荷に耐えられません
セグメント木を使用した場合：
- 構築：O(n) 一度だけのセットアップ
- 各クエリ：O(log n) ≈ 20操作
- 各更新：O(log n) ≈ 20操作
- 合計負荷：(10,000 × 20) + (5,000 × 20) = 300,000操作/秒 ✓
重要なポイント：頻繁な更新と大量データへの頻繁なクエリがある場合、セグメント木のO(log n)の両方の操作が不可欠になります。
セグメント木が実際に行うこと
セグメント木は、配列セグメントに関する情報を格納する二分木です。各ノードは範囲を表し、その範囲に対する演算（合計など）の結果を格納します。
会社の部門を整理することと考えてください：
- ルートノード：「会社全体の総予算は？」
- 内部ノード：「この部門の総予算は？」
- リーフノード：「この特定のチームの予算は？」
操作の仕組み
BUILD操作 - 「セグメントを階層的に整理する」
配列 [100, 200, 150, 80] からセグメント木を構築する場合：
- 各要素のリーフノードを作成（範囲[0,0]、[1,1]などを表す）
- 各親は子の合計を格納
- ルートは配列全体の合計を含む
- 木構造により効率的な範囲クエリが可能になります
[530] <- [0,3]の合計
/ \
[300] [230] <- [0,1]と[2,3]の合計
/ \ / \
[100] [200] [150] [80] <- 個別要素
0 1 2 3 <- 配列インデックスQUERY操作 - 「任意の範囲の合計を取得」
範囲[1, 3]をクエリする場合：
- ルートから開始し、現在の範囲がクエリ範囲と重なるかチェック
- 完全に含まれる場合：格納された合計を返す
- 部分的に重なる場合：両方の子を再帰的にチェック
- 重なるセグメントの結果を組み合わせる
UPDATE操作 - 「値を変更し、すべての合計を維持」
インデックス2を180に更新する場合：
- インデックス2のリーフノードを更新
- すべての祖先ノードを再帰的に更新
- 各影響を受けたノードが合計を再計算
- すべての範囲合計が自動的に正しく保たれます
これらの操作が発生するタイミング
これらの操作は、必要に応じて明示的に呼び出されます：
const segTree = SegmentTree.build([100, 200, 150, 80], 0, 3);
// QUERY: インデックス1から3の株式の合計を取得
let portfolioValue = segTree.rangeQuery(1, 3); // 430を返す
// UPDATE: インデックス2の株価が180に上昇
segTree.update(2, 180);
// QUERY: 更新後の新しい合計を取得
portfolioValue = segTree.rangeQuery(1, 3); // 460を返すセグメント木の素晴らしさは、一度構築されると、範囲サイズに関係なく、クエリと更新の両方がO(log n)時間で実行されることです！
最も重要な洞察
すべての範囲は、木に格納されたO(log n)個の重複しないセグメントに分解できます - 範囲を再帰的に半分に分割することで、任意の範囲クエリが最大O(log n)個のノードを訪問する木を作成し、クエリと更新の両方で対数時間を実現します。
覚えておくこと：アルゴリズムの天才性は、特定の「2のべき乗のような」セグメントの結果を事前計算することにあります。各レベルで決定する必要があるのは：「このセグメントは完全に内側、完全に外側、それとも部分的にクエリ範囲と重なっているか？」という単純な判断です。この各ノードでの単純な決定が、任意の範囲クエリに効率的に答えるために適切なセグメントを自動的に組み合わせます。
決定フレームワーク
セグメント木には3つの重要な決定があります：
構築時（分割統治）：
- 範囲を再帰的に半分に分割
- ボトムアップでノードを作成
- 親のために子の値を組み合わせる
クエリ時（範囲重複チェック）：
- 重複なし：このサブツリー全体をスキップ
- 完全な重複：このノードの値を直接返す
- 部分的な重複：両方の子をクエリして組み合わせる
更新時（変更の伝播）：
- リーフノードを更新
- 親を子の合計として再計算
- ルートまで伝播
コード
class SegmentTree {
constructor(segmentSum, leftBoundary, rightBoundary) {
// このノードが格納するもの
this.sum = segmentSum;
// このノードが表す範囲 [leftBoundary, rightBoundary] 両端含む
this.leftBoundary = leftBoundary;
this.rightBoundary = rightBoundary;
// 木構造
this.leftChild = null;
this.rightChild = null;
}
// BUILD: 配列から木を作成 - O(n)時間
static build(array, startIndex, endIndex) {
const isSingleElement = startIndex === endIndex;
// DECISION FRAMEWORK: ベースケース - 単一要素のリーフノード
if (isSingleElement) {
const elementValue = array[startIndex];
return new SegmentTree(elementValue, startIndex, endIndex);
}
// DECISION FRAMEWORK: 範囲を半分に分割
const midpoint = Math.floor((startIndex + endIndex) / 2);
const leftHalfEnd = midpoint;
const rightHalfStart = midpoint + 1;
// 両半分を再帰的に構築
const leftSubtree = SegmentTree.build(array, startIndex, leftHalfEnd);
const rightSubtree = SegmentTree.build(array, rightHalfStart, endIndex);
// DECISION FRAMEWORK: 組み合わせ - 親は子の合計を格納
const combinedSum = leftSubtree.sum + rightSubtree.sum;
const parentNode = new SegmentTree(combinedSum, startIndex, endIndex);
// 木構造を接続
parentNode.leftChild = leftSubtree;
parentNode.rightChild = rightSubtree;
return parentNode;
}
// UPDATE: array[targetIndex]をnewValueに変更 - O(log n)時間
update(targetIndex, newValue) {
// 境界チェック - インデックスはこのノードの範囲内でなければなりません
const indexOutOfBounds = targetIndex < this.leftBoundary ||
targetIndex > this.rightBoundary;
if (indexOutOfBounds) {
// インデックスがこのサブツリーに属していない - 更新不要
return;
}
const isLeafNode = this.leftBoundary === this.rightBoundary;
const leafContainsTarget = isLeafNode &&
(this.leftBoundary === targetIndex);
// DECISION FRAMEWORK: ターゲットリーフを見つけた
if (leafContainsTarget) {
this.sum = newValue;
return;
}
// DECISION FRAMEWORK: どの子がtargetIndexを含むか？
const midpoint = Math.floor((this.leftBoundary + this.rightBoundary) / 2);
const targetIsInRightHalf = targetIndex > midpoint;
if (targetIsInRightHalf) {
this.rightChild.update(targetIndex, newValue);
} else {
this.leftChild.update(targetIndex, newValue);
}
// DECISION FRAMEWORK: 変更を上方に伝播
const updatedLeftSum = this.leftChild.sum;
const updatedRightSum = this.rightChild.sum;
this.sum = updatedLeftSum + updatedRightSum;
}
// QUERY: 範囲[queryStart, queryEnd]の合計を取得 - O(log n)時間
rangeQuery(queryStart, queryEnd) {
// 境界チェック - このノードの範囲と重複なし
const noOverlap = queryEnd < this.leftBoundary ||
queryStart > this.rightBoundary;
if (noOverlap) {
// クエリ範囲がこのサブツリーと全く重ならない
return 0;
}
// クエリ範囲がこのノードの範囲とどう関係するかチェック
const exactMatch =
queryStart === this.leftBoundary && queryEnd === this.rightBoundary;
// DECISION FRAMEWORK: 完全な重複 - 事前計算された合計を使用
if (exactMatch) {
return this.sum;
}
// このノードの範囲の分割点を見つける
const midpoint = Math.floor((this.leftBoundary + this.rightBoundary) / 2);
const leftHalfEnd = midpoint;
const rightHalfStart = midpoint + 1;
// DECISION FRAMEWORK: 子との重複を決定
const queryIsEntirelyInRightHalf = queryStart >= rightHalfStart;
const queryIsEntirelyInLeftHalf = queryEnd <= leftHalfEnd;
if (queryIsEntirelyInRightHalf) {
// クエリは右サブツリーのみが必要
return this.rightChild.rangeQuery(queryStart, queryEnd);
}
if (queryIsEntirelyInLeftHalf) {
// クエリは左サブツリーのみが必要
return this.leftChild.rangeQuery(queryStart, queryEnd);
}
// DECISION FRAMEWORK: クエリが両方の子にまたがる - 分割して組み合わせる
const leftPortion = this.leftChild.rangeQuery(queryStart, leftHalfEnd);
const rightPortion = this.rightChild.rangeQuery(rightHalfStart, queryEnd);
const totalSum = leftPortion + rightPortion;
return totalSum;
}
}
// === 使用例: リアルタイム取引システム ===
// デモンストレーション用に8銘柄の小規模版をシミュレート
const stockPrices = [100, 200, 150, 80, 250, 300, 175, 220];
// セグメント木を構築 - O(n) 一度だけのコスト
console.log("取引システムのセグメント木を構築中...");
const tradingSystem = SegmentTree.build(stockPrices, 0, 7);
// 同時に発生する急速なクエリと更新をシミュレート
console.log("\n=== 高頻度取引活動のシミュレーション ===");
// 異なるユーザーからの複数の範囲クエリ
console.log("\nユーザークエリ（同時に発生）：");
console.log(`トレーダーA - ポートフォリオ[2-5]: $${tradingSystem.rangeQuery(2, 5)}`); // 805
console.log(`トレーダーB - ポートフォリオ[0-3]: $${tradingSystem.rangeQuery(0, 3)}`); // 530
console.log(`トレーダーC - ポートフォリオ[4-7]: $${tradingSystem.rangeQuery(4, 7)}`); // 945
// リアルタイムで発生する市場更新
console.log("\n市場更新: 株式3が$80から$120に跳ね上がりました");
tradingSystem.update(3, 120);
// 新しいクエリはすぐに変更を反映
console.log("\n市場変更後のクエリ（即座に反映）：");
console.log(`トレーダーA - ポートフォリオ[2-5]: $${tradingSystem.rangeQuery(2, 5)}`); // 845
console.log(`トレーダーD - ポートフォリオ[1-4]: $${tradingSystem.rangeQuery(1, 4)}`); // 690
// 別の急速な更新
console.log("\n市場更新: 株式5が$300から$250に下落");
tradingSystem.update(5, 250);
// さらに同時クエリ
console.log("\nさらなるユーザークエリ：");
console.log(
`トレーダーE - 全ポートフォリオ[0-7]: $${tradingSystem.rangeQuery(0, 7)}`
); // 1545
console.log(
`トレーダーF - 高価値株式[4-7]: $${tradingSystem.rangeQuery(4, 7)}`
); // 895
// 素晴らしさ: これらの操作はすべて各々O(log n)時間で実行されました！
// 本番環境でn = 1,000,000の場合、それでもクエリ/更新ごとに約20操作だけです疑問解消
よくある疑問 #1：「木が[0,1]や[2,3]のようなセグメントに分割される場合、[0,2]をどうやってクエリできますか？その範囲を正確に格納するノードがありません！」
なぜこれが不可能に見えるか
木構造を見ると、こう思うかもしれません：
[0,3]
/ \
[0,1] [2,3]
/ \ / \
[0] [1] [2] [3][0,2]を表す単一のノードはありません。ではどうやってクエリできるのでしょうか？
重要な洞察：複数のノードを組み合わせる
すべての可能な範囲に対して単一のノードは必要ありません！ セグメント木は複数のノードの結果を組み合わせます：
// クエリ[0,2]は以下に分解されます：
query(0, 2) = query(0, 1) + query(2, 2)
= node[0,1].sum + node[2].sum
= 300 + 150 = 450アルゴリズムがクエリ[0,2]を処理する方法は次のとおりです：
- ルート[0,3]から開始 - クエリ範囲[0,2]は部分的に重なる
- 中間点(1)でクエリを分割：
- 左の子[0,1]: クエリ[0,1] - 完全な重複、合計を返す
- 右の子[2,3]: クエリ[2,2] - 部分的な重複、さらに深く
- [2,3]で再度分割：
- 左の子[2]: クエリ[2,2] - 完全な重複、合計を返す
- 組み合わせ: [0,1]からの合計 + [2]からの合計 = 答え！
クエリ[0,2]の視覚的な分解：
クエリ[0,2]:
[0,3] "クエリを分割"
/ \
[0,1]✓ [2,3] "部分的"
/ \
[2]✓ [3]✗
返す: [0,1].sum + [2].sum魔法：任意の範囲[L,R]は、木にすでに格納されている最大O(log n)個の重複しないセグメントに分解できます。レベルごとに2つ以上のノードは必要ないため、8要素木での[1,6]のようなクエリでも、最大2×log₂(8) = 6ノードしか触れません。
よくある疑問 #2：「なぜ累積和配列を使わないのですか？prefixSum[i] = 0からiまでの要素の合計を維持すれば、prefixSum[R] - prefixSum[L-1]でO(1)時間で任意の範囲クエリに答えられます。」
なぜ累積和が優れていると思うかもしれません
累積和配列は範囲クエリに優れているように見えます：
// 累積和アプローチ
prefixSums = [0, 100, 300, 450, 530, 780, 1080];
// クエリ[2,5] = prefixSums[6] - prefixSums[2] = 1080 - 300 = 780
// O(1)クエリ時間 - O(log n)より良いように見えます！これは絶対に正しいです...値を更新する必要がない場合は。累積和アプローチは、頻繁なクエリがある静的配列に最適です。
なぜ累積和が更新で崩れるか
ここで問題が発生します：
// インデックス2を150から180に更新
// 今、インデックス2以降のすべての累積和を更新する必要があります：
prefixSums[3] = 480 (450だった)
prefixSums[4] = 560 (530だった)
prefixSums[5] = 810 (780だった)
prefixSums[6] = 1110 (1080だった)
// これは更新ごとにO(n)時間かかります！頻繁な更新がある場合、累積和はボトルネックになります。m回の更新とq回のクエリがある場合：
- 累積和：更新あたりO(n) × m回の更新 = O(m·n)合計
- セグメント木：更新あたりO(log n) × m回の更新 = O(m·log n)合計
重要なトレードオフ
累積和を使用するとき：
- 配列が静的（更新なし）または更新がまれ
- O(1)クエリ時間が必要
- 例：履歴データの累積統計の計算
セグメント木を使用するとき：
- クエリと更新の両方が頻繁
- 両方の操作にO(log n)で十分
- 例：リアルタイムポートフォリオ値を表示するライブダッシュボード
効率の違いを示す具体例
100万銘柄の取引システムを考えます（n = 1,000,000）：
シナリオ：毎秒10,000回のクエリと10,000回の更新
累積和の場合：
- 各更新：O(n) = 1,000,000操作
- 10,000回の更新 = 毎秒100億操作
- システムがクラッシュ！💥
セグメント木の場合：
- 各更新：O(log n) = 約20操作
- 10,000回の更新 = 毎秒200,000操作
- 各クエリ：O(log n) = 約20操作
- 10,000回のクエリ = 毎秒200,000操作
- 合計：毎秒400,000操作 - 完全に管理可能！✓
なぜセグメント木の構造が高速更新を可能にするか
魔法は更新の伝播方法にあります：
セグメント木でインデックス2を更新する場合：
[1110] <- これだけを更新
/ \
[250] [860] <- これだけを更新
/ \ / \
[100] [150] [180] [80] <- これだけを更新
↑
変更された値
O(log n)個のノードだけが更新を必要 - 木のレベルごとに1つ！これを、すべての後続の合計を更新する必要がある累積和と比較してください。木構造は、任意の更新の「影響範囲」をリーフからルートへのパスだけに制限します。
結論
セグメント木は、わずかに遅いクエリ（O(log n)対O(1)）を、劇的に速い更新（O(log n)対O(n)）と引き換えにします。データが頻繁に変更される場合、このトレードオフは不可欠です。両方の操作に対する対数保証により、セグメント木は動的範囲クエリ問題の第一選択肢となります。