セグメント木

01 / 一文で言うと

平衡二分木の各ノードに、ある範囲の集約値(和・最小・最大・gcd など)を持たせる。任意の区間は O(log N) 個の「正規分割片」に分解でき、それらは既にノードとして存在しているので、区間クエリも点更新も O(N) ではなく O(log N)。

問題区間和 + 一点更新入力[2,5,1,4,9,3,7,6]クエリ[1,5]更新a[3] = 10

長さ 8 の配列。連続区間の和を各ノードが保持する二分木を構築する。

ステップ

0 / 36

フェーズ

構築

現在

—

0 / 36

仕様

02 / パターンの骨格

# ノードは [l, r] を覆う;agg = 和 (または min / max / gcd / …)def build(node, l, r):if l == r: tree[node] ← arr[l]; returnm ← (l + r) // 2build(2·node, l, m);  build(2·node+1, m+1, r)tree[node] ← tree[2·node] + tree[2·node+1]# クエリ [ql, qr] — 内側の正規分割片を足し上げるdef query(node, l, r, ql, qr):if qr < l or r < ql: return 0if ql ≤ l and r ≤ qr: return tree[node]m ← (l + r) // 2return query(2·node, l, m, ql, qr) + query(2·node+1, m+1, r, ql, qr)

03 / このパターンを使うべき合図

「区間和 / 最小 / 最大 / gcd + 点更新」

最も典型的なトリガー。配列は変わる(点更新)が、任意の区間で集約値を問い続ける。累積和は更新無しの兄弟、セグメント木はその更新可能ないとこ。更新が一切ないなら累積和で十分。

「個数を数える / 区間和の個数」

古典的な「転倒数」系(LC 315、327、493)— キーをソートまたは座標圧縮し、頻度セグメント木を維持しながら走査する。各新要素について「これまでにこの範囲に幾つあったか」を区間クエリで答える。

「区間更新 + 区間クエリ」

上位版。遅延伝播を足す:各ノードが子へ降ろすべき修正を保持し、再帰がそのノードを通る瞬間に下ろす。同じ O(log N) のまま、両方とも区間レベルに。

「修正付きの区間 / イベント / 被覆」

使う x 座標すべてを座標圧縮して小さな配列に押し込めば、セグメント木が各圧縮位置の現在状態(個数、最大高さなど)を保持する。スカイライン、矩形被覆、カレンダー予約 — 全部この仕組みに帰着する。

04 / よくある落とし穴

右半分の +1 を忘れる。

再帰は build(2·node, l, m) と build(2·node+1, m+1, r) — 右の子は m+1 から始まり、 m ではない。ここで 1 ずれると、arr[m] を二重に数えるか、こっそり落とすか、片寄りに応じてどちらかが起きる。

先に累積和を選んで、後から更新が必要だと気づく。

累積和はクエリ O(1) だが更新 O(N)。問題が「arr[i] を変える」と言った瞬間に再構築が必要 — そこでセグメント木(和なら Fenwick 木)に軍配が上がる。最初の段階で可変性を見抜くこと。

木配列のサイズを取り違える。

安全な確保は 4·N。厳密な上界は 2·次の 2 のべき(N) だが、 4·N ならその計算を飛ばせるし、2N で 1 つ足りない稀なケースも避けられる。小さく取ると範囲外書き込みでデバッグが苦しい。

05 / LeetCode で練習