Spaghetti Source logo

区分木

説明

実数の区間のリストが与えられる.点(実数)p が与えられたとき,p を含む区間をすべて列挙する問題を一次元の点位置決定問題という.この問題に答えるデータ構造として区分木(segment tree)と呼ばれるものがある.区間木は次のような構造を持つ.

自分の親にすでに管理されている区間を繰り返し保持しないようにすれば,区分木のサイズは O(n log n) である.与えられた点 p を含む区間の列挙は,二分探索と区間内の値の報告の分だけ計算量がかかるので O(log n + k) となる.ただし k は p を含む区間の総数.

なお,空間計算量を O(n) にするデータ構造として区間木(interval tree)と呼ばれるものもある.これは頂点 v が保持するものを v の中間値をまたぐ区間(左端でソートされたものと右端でソートされたものを両方持つ)とし,左右の子は中間値をまたがない区間とするものである(詳しくは計算幾何の参考書を参照).ただしプログラムコンテストでは(log n 増し程度の)空間計算量が問題となることは少ないので,区分木で普通は十分だと思う.

計算量

使い方

開区間を扱いたい場合はあらかじめ区間を微小に縮小しておく.閉区間を扱いたい場合も同様に微小に拡大しておく.

ソースコード

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

struct segment_tree {
  vector<position> pos;
  struct node {
    vector<contents> values;
    position B, E, M;
    node *left, *right;
  } *root;
  template <class IN>
  segment_tree(IN begin, IN end) : pos(begin, end) {
    root = build_tree(0, pos.size()-1);
  }
  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);
  }
};

Verified

前原 貴憲(contact_at_prefield.com).

Last Modified: 2007.05.25 21:49:39.