区間木

説明

区間木は一次元の点位置決定問題に答える静的なデータ構造である．具体的には以下のことが行える．

• 点クエリ: 与えられた点 x を含む半開区間を全列挙
• 区間クエリ: 与えられた半開区間 [a,b) と重なる半開区間を全列挙

以下の実装は点クエリについてのみである．

区間木の本来の形は静的に固定された座標の上で自由に insert / erase が行えるデータ構造だが，erase は実装していない．insert と同じコードで insert されたであろう場所を手繰り，そこで erase をかければできるが．

計算量

• 前処理: O(n log n)．
• 点クエリ: O(log n + k)，ただし k は hit 数．
• 区間クエリ: O(log n + k)，ただし k は hit 数．

使い方

• position は区間の端点が表す全順序．
• contents は区間に対応させる値．追加部分とあわせて問題に応じて柔軟に設定する．

• interval_tree に短点のリストを sort/unique したものを食わせる．
• insert で区間を食わせる．端点は期化時に食わせたものの中に入っている必要がある．
• query で点を含む区間に対応している値を拾ってくる．

ソースコード

typedef int position;
typedef int contents;
struct interval {
  position low, high;
  interval(position low, position high) :
    low(low), high(high) { }
};

struct interval_tree {
  vector<position> pos;
  struct node {
    vector<contents> values;
    position B, E, M;
    node *left, *right;
  } *root;

  template <class IN>
  interval_tree(IN begin, IN end) : pos(begin, end) {
    root = build_tree(0, pos.size()-1);
  }
  ~interval_tree() { release(root); }

  node *build_tree(int i, int j) {
    int m = (i+j)/2;
    node *t = new node;
    t->B = pos[i]; t->E = pos[j]; t->M = pos[m];
    t->left  = (i+1 < j ? build_tree(i, m) : NULL);
    t->right = (i+1 < j ? build_tree(m, j) : NULL);
    return t;
  }
  void insert(const interval& I, contents c) { insert(root, I, c); }
  void insert(node *v, const interval& I, contents c) {
    if (I.low <= v->B && v->E <= I.high) {
      v->values.push_back( c );
    } else {
      if (I.low  < v->M) insert(v->left , I, c);
      if (I.high > v->M) insert(v->right, I, c);
    }
  }
  template <class OUT>
  void query(position p, OUT out) { query(root, p, out); }
  template <class OUT>
  void query(node *t, position p, OUT out) {
    if (!t || p < t->B || p >= t->E) return;
    copy(t->values.begin(), t->values.end(), out);
    if (p < t->M) query(t->left, p, out);   // 半開区間の探索になる
    else          query(t->right, p, out);
  }
  void release(node *t) {
    if (t->left) release(t->left);
    if (t->right) release(t->right);
    delete t;
  }
};

Verified

• UVA 10535 (Shooter) 1297 MS, 644 KB