差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:segment_tree [2019/11/13] – [セグメント木] ikatakos | programming_algorithm:data_structure:segment_tree [2019/11/13] – ikatakos | ||
---|---|---|---|
行 24: | 行 24: | ||
例えば区間和なら $a+b=c$ → $c-a=b$ なので、(区間$[l, | 例えば区間和なら $a+b=c$ → $c-a=b$ なので、(区間$[l, | ||
最小値や最大値はこうはいかない。 | 最小値や最大値はこうはいかない。 | ||
+ | |||
+ | 数学的には、[[wpjp> | ||
+ | モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\dot$ の組合せの内、以下の条件を満たすものである。 | ||
+ | |||
+ | * 結合律が成り立つ=計算の順序を入れ替えてもいい | ||
+ | * $(a \dot b) \dot c = a \dot (b \dot c)$ | ||
+ | * 単位元が存在する | ||
+ | * $S$ のどんな要素 $a$ に対しても影響を及ぼさない要素 $e$ が存在する | ||
+ | * $a \dot e = e \dot a = a$ | ||
+ | |||
+ | 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, | ||
+ | |||
+ | 単位元が存在しない例としては、自然数と足し算があげられる。 | ||
+ | |||
+ | ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。 | ||
+ | 例えば単位元が無い自然数上の足し算は、(初期値などに制約はあるが)セグメント木で実装できる。 | ||
=====一点更新・区間取得===== | =====一点更新・区間取得===== |