セグメント木 (Segment Tree)

区間に対するクエリ（区間和・区間最小など）と一点更新を $\mathcal{O}(\log N)$ で処理する木構造。競技プログラミングの主力データ構造。

要点

• 配列を完全二分木に乗せ、各内部ノードに子区間の集約値を持たせる
• モノイド で抽象化でき、結合則を満たす任意の演算（和・min・max・gcd 等）に適用可能
• 遅延評価 (lazy propagation) により区間更新も $\mathcal{O}(\log N)$ で扱える

空間分割木（関連）

• 四分木 (Quadtree) — 2 次元空間を再帰 4 分割し、衝突判定などを高速化する。モートン符号（Z オーダー曲線）で領域をインデックス化する。

関連する探索テクニック

• 01-BFS — 辺コストが 0 か 1 のグラフで deque を使い最短路を線形時間で求める。セグ木とは別だが競プロ頻出の最短路高速化。

関連: balanced-search-tree / competitive-programming-heuristics / _moc-algorithm