差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:segment_tree [2019/11/13] – [セグメント木] ikatakos | programming_algorithm:data_structure:segment_tree [2019/11/13] – ikatakos | ||
---|---|---|---|
行 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, | ||
行 40: | 行 40: | ||
ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。 | ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。 | ||
例えば単位元が無い自然数上の足し算は、(初期値などに制約はあるが)セグメント木で実装できる。 | 例えば単位元が無い自然数上の足し算は、(初期値などに制約はあるが)セグメント木で実装できる。 | ||
+ | |||
+ | =====indexの表現方法===== | ||
+ | |||
+ | セグメント木には、2つのindex(っぽい概念)が登場する。 | ||
+ | |||
+ | * (1) updateやqueryで与えられる $a_i$ の $i$ を指すindex | ||
+ | * (2) 二分木を1つの配列で表現する実装において、その配列上のindex | ||
+ | |||
+ | 1 | ||
+ | / | ||
+ | | ||
+ | / \ / \ | ||
+ | 4 5 6 7 | ||
+ | || || || || 対応 | ||
+ | a1 a2 a3 a4 ←(1) | ||
+ | |||
+ | indexは、0始まりか1始まりかを意識する必要がある。 | ||
+ | |||
+ | プログラム全般的には、多くの言語で配列の添字が0-indexなのでそれに倣うことが多いが、 | ||
+ | 特に(2)の二分木の実装では、1-indexにした方が都合が良い。 | ||
+ | |||
+ | 2進数にしたとき、深さと桁数が一致する。また、子のindexを右bitshiftすると親になるので、親子を辿るindexの計算が簡潔になる。 | ||
+ | |||
+ | 0001 | ||
+ | / | ||
+ | 0010 0011 | ||
+ | / \ / \ | ||
+ | 0100 0101 0110 0111 | ||
=====一点更新・区間取得===== | =====一点更新・区間取得===== |