差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:sparse_table [2019/12/04] – ikatakos | programming_algorithm:data_structure:sparse_table [2019/12/04] – ikatakos | ||
---|---|---|---|
行 14: | 行 14: | ||
足し算は冪等性を満たさないため、使えない。 | 足し算は冪等性を満たさないため、使えない。 | ||
- | (別に使ってもいいのだが、区間を被らせずにクエリを処理するのは計算量 $O(\log{N})$ かかるし、 | + | (別に使ってもいいのだが、クエリ処理に計算量 $O(\log{N})$ かかるようになるし、 |
それならセグメント木と同じ上にこちらは更新も出来るので、あまり優位性がない) | それならセグメント木と同じ上にこちらは更新も出来るので、あまり優位性がない) | ||
+ | |||
+ | min, maxの他には、最小公倍数/ | ||
===== データ構造 ===== | ===== データ構造 ===== |