差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
| programming_algorithm:data_structure:sparse_table [2022/07/15] – ikatakos | programming_algorithm:data_structure:sparse_table [2023/10/13] (現在) – ikatakos | ||
|---|---|---|---|
| 行 2: | 行 2: | ||
| * [[http:// | * [[http:// | ||
| + | |||
| + | < | ||
| ===== 概要 ===== | ===== 概要 ===== | ||
| 行 13: | 行 15: | ||
| * 更新はできない | * 更新はできない | ||
| - | 足し算は冪等性を満たさないため、使えない。 | + | 足し算は冪等性を満たさないため、使えない。\\ |
| - | （別に使えるように改変はできるのだが、クエリ処理に $O(\log{N})$ かかるようになるし、 | + | データの持たせ方を工夫した DisjointSparseTable なら可能。（ただ、そもそも足し算なら累積和で区間クエリには答えられる） |
| - | それならセグメント木と同じ上にそちらは更新も出来るので、あまり優位性がない） | + | |
| + | * [[programming_algorithm: | ||
| + | |||
| + | min, maxの他には、最小公倍数/ | ||
| - | min, maxの他には、最小公倍数/ | ||
| ===== データ構造 ===== | ===== データ構造 ===== | ||
