差分

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

この比較画面にリンクする

両方とも前のリビジョン 前のリビジョン
programming_algorithm:data_structure:segment_tree [2019/11/13]
ikatakos [セグメント木]
programming_algorithm:data_structure:segment_tree [2019/11/13] (現在)
ikatakos
行 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 · 最終更新: 2019/11/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0