「この区間の和、早く教えて」
配列 [5, 8, 6, 3, 2, 7, 2, 6] があるとします。誰かが尋ねます。「2番から5番まで全部足すといくつ?」(6+3+2+7 = 18)
1回なら足すだけです。でもこんな質問が数十万回来て、途中で値も変わるとしたら? 毎回区間を最初から足すとクエリ1つでO(n) — すぐに時間切れです。
例: 区間和
query(2, 5)→ 18。その後arr[4]を2から10に変えると、再びquery(2, 5)→6+3+10+7 = 26。
累積和ではダメ? (半分だけ正解)
「先に全部足しておこう」という発想が累積和(prefix sum)です。prefix[i] に0..iの合を保存しておけば、区間和は prefix[r] - prefix[l-1] でO(1)で終わります。
クエリだけ見れば完璧です。問題は更新です。arr[4] 一つ変えただけで、その後ろの prefix[4], prefix[5], ... が全部狂います。更新1回で再びO(n)を使うことになります。
- •累積和: クエリ O(1) / 更新 O(n) ← 頻繁に変わると致命的
- •私たちが欲しいもの: クエリも更新も両方速く
なぜツリーでまとめる? — 「区間を先に合わせておく」
ここで発想を変えます。配列を区間(segment)単位に細かく分け、各区間の合を先にノードに書いておくのです。
- •葉: 要素1個(
[4-4]) - •内部ノード: 2つの子区間を合わせた区間(
[4-5],[4-7]…) - •ルート: 全体(
[0-7])
すると面白いことが起きます。[2-5] の和を求めるとき、ちょうど2つのノード [2-3](合9)と [4-5](合9)を選んで足すだけで 18 になります。要素4個を一つずつ足したのではなく、先に合わせておいた塊2つを合わせたのです。
核心は親の合 = 2つの子の合というルールです。おかげでどんな区間でも O(log n) 個のノードの破片で覆えます。
更新も一筋だけ直せば完了
値が変わったらどうするか? arr[4] を10に変えるなら:
1. [4-4] の葉を10に
2. その親 [4-5] を再合算(9 → 17)
3. さらにその親 [4-7](17 → 25)
4. ルート [0-7](39 → 47)
葉からルートまでちょうど一筋(path)のノードだけ足し直せば済みます。ツリーの高さは log n なので、更新もO(log n)。累積和のO(n)更新とは次元が違います。
均衡が核心です。 セグメントツリーはクエリもO(log n)、更新もO(log n)で*両方*速い。値が変わり続ける状況で真価を発揮します。
自分の目で確かめる
葉からルートまでツリーが少しずつ積み上がり、クエリが区間に沿って下りながら重なるノードだけ選んで合わせ、更新が葉からルートまで一筋を辿って合を直す全工程をステップ別の可視化で用意しました。各ノードが担当する区間と合が一目で分かります。