セグメント木（区間和・区間最小）
配列の要素を更新すると葉から根へ光が伝播して再計算され、区間 [l, r) を問うと必要なノードだけが点灯します。更新も問い合わせも O(log n)。
8
1
6
配列（数字をクリック → 値が +1、根まで光が伝播）
クリックで +1（9 を超えると 0 に戻る）。区間 [l, r) はオレンジ枠。
クエリ区間
—
区間和
—
走査ノード数
—
単純加算なら
—
セグメント木（葉＝配列、上に向かって集約。更新で赤い光が根へ、問い合わせで緑のノードが選ばれる）
セグメント木は、配列を底辺（葉）に並べ、隣り合う 2 つをまとめた集約値を親に持つ完全二分木です。
各内部ノードは「自分の下にある区間全体の集約（和や最小）」を覚えています。
1 つの要素を更新すると、その葉から根までの
区間
1 つの要素を更新すると、その葉から根までの
log n 個のノードだけを下から塗り直せば木全体が整合します（赤い光の伝播）。区間
[l, r) の問い合わせでは、その区間をぴったり覆う「なるべく大きいノード」を貪欲に選びます。区間にすっぽり収まるノードは即採用し、はみ出すノードだけ左右の子に分割するので、選ばれるノードは O(log n) 個で済みます。
いま何が起きている？
ここがポイント
- 親 = 子2つの集約 ── 内部ノードは
左の子 op 右の子。和なら加算、最小なら min。 - 更新は葉→根の1本道 ── 変わるのは
log n個だけ。だから 1 点更新がO(log n)。 - 問い合わせは区間を覆うノードを貪欲選択 ── ぴったり収まれば即採用、はみ出せば子へ分割。選ぶノードは高々
O(log n)個。 - op は結合的なら何でも ── 和・最小・最大・gcd など。単位元（和なら 0、min なら +∞）で空区間を扱う。