差分
このページの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 | ||
| + | |||
| + | １ | ||
| + | / | ||
| + | | ||
| + | / \ / \ | ||
| + | ４ ５ ６ ７ | ||
| + | || || || || 対応 | ||
| + | a1 a2 a3 a4 ←(1) | ||
| + | |||
| + | indexは、0始まりか1始まりかを意識する必要がある。 | ||
| + | |||
| + | プログラム全般的には、多くの言語で配列の添字が0-indexなのでそれに倣うことが多いが、 | ||
| + | 特に(2)の二分木の実装では、1-indexにした方が都合が良い。 | ||
| + | |||
| + | 2進数にしたとき、深さと桁数が一致する。また、子のindexを右bitshiftすると親になるので、親子を辿るindexの計算が簡潔になる。 | ||
| + | |||
| + | 0001 | ||
| + | / | ||
| + | 0010 0011 | ||
| + | / \ / \ | ||
| + | 0100 0101 0110 0111 | ||
| =====一点更新・区間取得===== | =====一点更新・区間取得===== | ||
