Segment tree

完全二分木を用いてRMQ(Range Minimum Query)などの処理を高速に行うデータ構造.

前処理,空間計算量 $O(N)$

必要なノードの個数(配列のサイズ) $2N-1$

二分木であることを考えたら当たり前かもしれない.

区間での最小値を求める処理,ある点に対する変更処理,共に各高さで定数個のノードにしかアクセスしない→ $O(\log N)$

自然数配列 $A$ ($|A| = N$)について半開区間 $[i,j)$ の最小値を求めるQueryと,$A_i$ を $x$ に変更するQueryをSegment treeを用いて処理する.

実装について考える.

配列のサイズは $2N-1$

一番上の親を0としてその子を1,2 さらにその子を3,4,5,6…と番号付けをしていく.

番号 $n$ のノードについて,

親 : $\lfloor (n-1)/2 \rfloor$

子 : $2n+1$ , $2n+2$

となる.(完全二分木の性質でもある)

初期化 : 配列の全要素をinfで埋めておく.

値の更新Query

$A_i$ を含む区間のノード全てについて値を計算し直す.