差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:data_structure:segment_tree [2019/11/13] – [セグメント木] ikatakosprogramming_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 b) \bullet c = a \bullet (b \bullet c)$
   * 単位元が存在する   * 単位元が存在する
     * $S$ のどんな要素 $a$ に対しても影響を及ぼさない要素 $e$ が存在する     * $S$ のどんな要素 $a$ に対しても影響を及ぼさない要素 $e$ が存在する
-    * $a \dot e = e \dot a = a$+    * $a \bullet e = e \bullet a = a$
  
 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, 4^{(3^2)}=262144$ 結合律が成り立たない例としては、実数と冪乗が挙げられる。$\displaystyle (4^3)^2=4096, 4^{(3^2)}=262144$
行 40: 行 40:
 ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。 ただし、モノイド→セグメント木が利用可能は真だが、逆は必ずしも真でない。
 例えば単位元が無い自然数上の足し算は、(初期値などに制約はあるが)セグメント木で実装できる。 例えば単位元が無い自然数上の足し算は、(初期値などに制約はあるが)セグメント木で実装できる。
 +
 +=====indexの表現方法=====
 +
 +セグメント木には、2つのindex(っぽい概念)が登場する。
 +
 +  * (1) updateやqueryで与えられる $a_i$ の $i$ を指すindex
 +  * (2) 二分木を1つの配列で表現する実装において、その配列上のindex
 +
 +        1
 +       /  \
 +     2    3     ←(2)
 +    / \    / \
 +  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
  
 =====一点更新・区間取得===== =====一点更新・区間取得=====
programming_algorithm/data_structure/segment_tree.txt · 最終更新: 2020/12/24 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0