Module cp_library_rs::data_structure::segment_tree

source ·
Expand description

セグメント木

集合 $S$ と演算 $\circ$ の組 $(S,\circ)$ がモノイド（Monoid）であるとき， $S$ の要素の列 $A$ に対し，

  • 区間積の取得 ： $A[l] \circ A[l+1] \circ \cdots \circ A[r]$
  • 要素の更新 ： $A[i] \leftarrow x$

をそれぞれ $O(\log N)$ で行う．（$N = |A|$）

Structs