差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:data_structure:sparse_table [2019/12/04] – ikatakos | programming_algorithm:data_structure:sparse_table [2019/12/04] – [実装] ikatakos | ||
---|---|---|---|
行 5: | 行 5: | ||
===== 概要 ===== | ===== 概要 ===== | ||
- | * 区間最小値/ | + | * 区間最小値/ |
- | * 演算 $\oplus$ は、以下の条件を満たす必要がある(min, | + | * 演算 $\oplus$ は、以下の条件を満たす必要がある(min, |
* 結合則: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$ | * 結合則: $(A \oplus B) \oplus C = A \oplus (B \oplus C)$ | ||
- | * 冪等性: $A \oplus | + | * 冪等性: $A \oplus |
* クエリ処理はとても速い $O(1)$ | * クエリ処理はとても速い $O(1)$ | ||
* 事前計算の計算量・メモリは少し多めに必要になる $O(N \log{N})$ | * 事前計算の計算量・メモリは少し多めに必要になる $O(N \log{N})$ | ||
行 14: | 行 14: | ||
足し算は冪等性を満たさないため、使えない。 | 足し算は冪等性を満たさないため、使えない。 | ||
- | (別に使ってもいいのだが、区間を被らせずにクエリを処理するのは計算量 $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: |