セグメント木

抽象化

集合 $S$、結合的な演算 $\cdot$、単位元 $e$ からなるモノイドを考える。セグメント木は配列の区間積

$a_l \cdot a_{l+1} \cdots a_{r-1}$

を $O(\log N)$ で求める。

典型例

演算	単位元
最小値	$+\infty$
最大値	$-\infty$
和	$0$
gcd	$0$

遅延評価を加える場合も、まず「何を区間に保持するか」「作用がどう合成されるか」を式にする。