差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:sparse_table [2019/12/04] – ikatakos | programming_algorithm:data_structure:sparse_table [2019/12/04] – ikatakos | ||
|---|---|---|---|
| 行 5: | 行 5: | ||
| ===== 概要 ===== | ===== 概要 ===== | ||
| - | * 区間最小値/ | + | * 区間最小値/ |
| - | * 演算 ⊕ は、以下の条件を満たす必要がある（min, | + | * 演算 ⊕ は、以下の条件を満たす必要がある（min, |
| * 結合則: (A⊕B)⊕C=A⊕(B⊕C) | * 結合則: (A⊕B)⊕C=A⊕(B⊕C) | ||
| - | * 冪等性: $A \oplus | + | * 冪等性: $A \oplus |
| * クエリ処理はとても速い O(1) | * クエリ処理はとても速い O(1) | ||
| * 事前計算の計算量・メモリは少し多めに必要になる O(NlogN) | * 事前計算の計算量・メモリは少し多めに必要になる O(NlogN) | ||
| 行 14: | 行 14: | ||
| 足し算は冪等性を満たさないため、使えない。 | 足し算は冪等性を満たさないため、使えない。 | ||
| - | （別に使ってもいいのだが、区間を被らせずにクエリを処理するのは計算量 O(logN) かかるし、 | + | （別に使ってもいいのだが、クエリ処理に計算量 O(logN) かかるようになるし、 |
| それならセグメント木と同じ上にこちらは更新も出来るので、あまり優位性がない） | それならセグメント木と同じ上にこちらは更新も出来るので、あまり優位性がない） | ||
| + | |||
| + | min, maxの他には、最小公倍数/ | ||
| ===== データ構造 ===== | ===== データ構造 ===== | ||
