差分
このページの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:// | ||
| - | 区間に対する処理をするときによく使われる。a1,a2,...,anの配列に対し、以下の2つを処理する。（一点更新区間取得） | + | 区間に対する処理をするときによく使われる。a1,a2,...,anの配列に対し、以下を処理する。（一点更新区間取得） |
| * 区間和のセグメント木(例) | * 区間和のセグメント木(例) | ||
| 行 24: | 行 24: | ||
| 例えば区間和なら a+b=c → c−a=b なので、(区間[l,r)の和)=(区間[1,r)の和)−(区間[1,l)の和) で求められる。 | 例えば区間和なら a+b=c → c−a=b なので、(区間[l,r)の和)=(区間[1,r)の和)−(区間[1,l)の和) で求められる。 | ||
| 最小値や最大値はこうはいかない。 | 最小値や最大値はこうはいかない。 | ||
| + | |||
| + | 数学的には、[[wpjp> | ||
| + | モノイドとは、例えば「整数全体」と「足し算」のように、ある要素の集合 S とその上での二項演算 ∙ の組合せの内、以下の条件を満たすものである。 | ||
| + | |||
| + | * 結合律が成り立つ＝計算の順序を入れ替えてもいい | ||
| + | * (a∙b)∙c=a∙(b∙c) | ||
| + | * 単位元が存在する | ||
| + | * S のどんな要素 a に対しても影響を及ぼさない要素 e が存在する | ||
| + | * a∙e=e∙a=a | ||
| + | |||
| + | 結合律が成り立たない例としては、実数と冪乗が挙げられる。(43)2=4096,4(32)=262144 | ||
| + | |||
| + | 単位元が存在しない例としては、自然数と足し算があげられる。 | ||
| + | |||
| + | ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。 | ||
| + | 例えば単位元が無い自然数上の足し算は、（初期値などに制約はあるが）セグメント木で実装できる。 | ||
| =====一点更新・区間取得===== | =====一点更新・区間取得===== | ||
