ei1333's page

ホーム > Wiki

分解可能問題

説明

クエリ問題が分解可能であるとは

ものをいう。ここでは分解可能問題に対する静的なデータ構造を与えられた時にインクリメンタルなデータ構造にしている。

計算量

$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$ オペレータを定義する必要がある。また, クエリに応答する際には, 添字演算子[] を使いデータ構造を取り出す。

template< class T >
struct DecomposableSearchingStructure
{
  struct DecomposableSearchingProblem
  {
    T structure;
    int length;

    DecomposableSearchingProblem(T t, int l) : structure(t), length(l) {}

    DecomposableSearchingProblem operator+(const DecomposableSearchingProblem &p)
    {
      return (DecomposableSearchingProblem(structure + p.structure, length + p.length));
    }
  };

  vector< DecomposableSearchingProblem > vs;

  DecomposableSearchingStructure() {}

  void add(const T &st)
  {
    vs.emplace_back(DecomposableSearchingProblem(st, 1));
    while(vs.size() > 1 && vs[vs.size() - 2].length == vs[vs.size() - 1].length) {
      DecomposableSearchingProblem renew(vs[vs.size() - 2] + vs[vs.size() - 1]);
      vs.pop_back(), vs.pop_back();
      vs.push_back(renew);
    }
  }

  size_t size()
  {
    return (vs.size());
  }

  T &operator[](int k)
  {
    return (vs[k].structure);
  }
};

問題例

参考資料