分解可能問題
説明
クエリ問題が分解可能であるとは
- 要素 $1$ つだけのデータ $[e]$ に対するクエリを $q([e])$ と表すとき, 要素列に対するクエリは $q([e_1, e_2, \dotsc, e_n]) = q([e_1]) \star q([e_2]) \star \dotsb \star q([e_n])$ となる演算子 $\star$ (結合法則を満たす) によって表すことができる
ものをいう。ここでは分解可能問題に対する静的なデータ構造を与えられた時にインクリメンタルなデータ構造にしている。
計算量
$n$ 要素の静的データ構造が $T(n)$ で構築できるとき, $n$ 回の追加にかかる計算量 $O(T(n)\log n)$
$n$ 要素の静的データ構造に対するクエリと $\star$ が $U(n)$ で応答できるとき, $n$ 回のクエリにかかる計算量 $O(U(n)\log n)$
実装例
静的なデータ構造 $T_1$ と $T_2$ を結合する $T_1 + T_2$ オペレータを定義する必要がある。また, クエリに応答する際には, 添字演算子[] を使いデータ構造を取り出す。
問題例
- 検証済ECR 16 F. String Set Queries (Submittion: #24912583)