差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:data_structure:sparse_table [2019/12/04] – ikatakos | programming_algorithm:data_structure:sparse_table [2019/12/05] – [実装] ikatakos | ||
|---|---|---|---|
| 行 16: | 行 16: | ||
| （別に使ってもいいのだが、クエリ処理に計算量 $O(\log{N})$ かかるようになるし、 | （別に使ってもいいのだが、クエリ処理に計算量 $O(\log{N})$ かかるようになるし、 | ||
| それならセグメント木と同じ上にこちらは更新も出来るので、あまり優位性がない） | それならセグメント木と同じ上にこちらは更新も出来るので、あまり優位性がない） | ||
| + | |||
| + | min, maxの他には、最小公倍数/ | ||
| ===== データ構造 ===== | ===== データ構造 ===== | ||
| 行 48: | 行 50: | ||
| PythonならNumPyを使えば、tableの構築において $k-1$ の計算結果を利用して $k$ を求める部分を高速化できる。 | PythonならNumPyを使えば、tableの構築において $k-1$ の計算結果を利用して $k$ を求める部分を高速化できる。 | ||
| + | （ただしminimum, | ||
| <sxh python> | <sxh python> | ||
| 行 69: | 行 72: | ||
| def query(self, l, r): | def query(self, l, r): | ||
| + | """ | ||
| d = r - l | d = r - l | ||
| if d == 1: | if d == 1: | ||
