差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:segment_tree [2019/11/13] – ikatakos | programming_algorithm:data_structure:segment_tree [2019/11/13] – [セグメント木] ikatakos | ||
|---|---|---|---|
| 行 4: | 行 4: | ||
| * [[http:// | * [[http:// | ||
| - | 区間に対する処理をするときによく使われる。$a_1, | + | 区間に対する処理をするときによく使われる。$a_1, |
| * 区間和のセグメント木(例) | * 区間和のセグメント木(例) | ||
| 行 26: | 行 26: | ||
| 数学的には、[[wpjp> | 数学的には、[[wpjp> | ||
| - | モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\dot$ の組合せの内、以下の条件を満たすものである。 | + | モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 $S$ とその上での二項演算 $\bullet$ の組合せの内、以下の条件を満たすものである。 |
| * 結合律が成り立つ＝計算の順序を入れ替えてもいい | * 結合律が成り立つ＝計算の順序を入れ替えてもいい | ||
| - | * $(a \dot b) \dot c = a \dot (b \dot c)$ | + | * $(a \bullet |
| * 単位元が存在する | * 単位元が存在する | ||
| * $S$ のどんな要素 $a$ に対しても影響を及ぼさない要素 $e$ が存在する | * $S$ のどんな要素 $a$ に対しても影響を及ぼさない要素 $e$ が存在する | ||
| - | * $a \dot e = e \dot a = a$ | + | * $a \bullet |
| 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, | 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, | ||
