セグメント木
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 / よくある落とし穴
i.
右半分の +1 を忘れる。
再帰は
build(2·node, l, m) と build(2·node+1, m+1, r) — 右の子は m+1 から始まり、 m ではない。ここで 1 ずれると、arr[m] を二重に数えるか、こっそり落とすか、片寄りに応じてどちらかが起きる。ii.
先に累積和を選んで、後から更新が必要だと気づく。
累積和はクエリ O(1) だが更新 O(N)。問題が「
arr[i] を変える」と言った瞬間に再構築が必要 — そこでセグメント木(和なら Fenwick 木)に軍配が上がる。最初の段階で可変性を見抜くこと。iii.
木配列のサイズを取り違える。
安全な確保は
4·N。厳密な上界は 2·次の 2 のべき(N) だが、 4·N ならその計算を飛ばせるし、2N で 1 つ足りない稀なケースも避けられる。小さく取ると範囲外書き込みでデバッグが苦しい。05 / LeetCode で練習
難易度順に 4 問。あえて解答は載せていません。