菜鳥でも分かる線分樹入門クラシック

線分ツリーの定義
まず、線分木は線分でも木でもあり、二叉木であり、各接点は線分であり、各線分の左右の息子線分はそれぞれその線分の左半と右半の区間であり、再帰的に定義された後は線分木であり、以下のように図示されている.
図1.線分ツリーの意図
線分ツリーのデータ構造の定義
struct Line{   int left, right, count;   Line *leftChild, *rightChild;   Line(int l, int r): left(l), right(r) {}
};
PS:countフィールドは、その線分がいくつかあることを示しています
線分ツリーの定義がわかったら、線分ツリーの適用例を挙げて説明します
例題:N本の線分,{[2,5],[4,6],[0,7]},M個の点{2,4,7}を与え,各点がそれぞれいくつかの線分に現れたことを判断する
問題を見て、ある人は第一に思いついたアルゴリズムはすべての点に対して、一つ一つの線分を遍歴して、簡単にすべての点がいくつかの線分に現れたことを判断して、小学生はすべてのアルゴリズムで、時間の複雑度はO(M*N)です
国Nが非常に大きく、例えば2^32-1、Mも非常に大きいM=2^32-1、O(M*N)のアルゴリズムは耐えられないので、この時、線分樹が盛大に登場しました
線分ツリーの解法:
1.まず、すべての線分をカバーできる最大区間を見つけ、すべての線分を巡り、線分の最値(左端点の最小値、右端点の最大値)を探すことで、この区間を決定することができ、{[2,5],[4,6],[0,7]}に対して、この区間は[0,7]、時間複雑度はO(N)である.
2.次に、この区間に基づいて線分木(図1参照)を1本建設し、時間複雑度O(log(MAX-MIN))
3.各線分Aについて、ルートノードからこの線分ツリーを巡回し、各現在巡回しているノードNODE(線分ツリーの各ノードは線分である)について、3つのケースを考慮する
a)線分Aが線分NODEの左半分区間に含まれている場合、NODEの左息子(実はNODEの左半分区間)からこの木を遍歴する
b)線分Aが線分NODEの右半分区間に含まれている場合、NODEの右息子(実はNODEの右半分区間)からこの木を遍歴する
c)線分Aが線分NODEとちょうど重なる場合、遍歴を停止し、NODEのcountフィールドに1を加算する
d)以上の場合を除き、線分Aの左半分をNODEの左息子に、Aの右半分をNODEの右息子に、
以上の手順については、分割後の各小線分が線分木にちょうど落ちるように、各線分を絶えず分割する作業を行い、例を挙げると、例えば分割[2,5]、まず[2,5]と[0,7]を比較し、状況dに合致し、Aを[2,3]と[4,5]に分ける.
I)に対して[2,3]に対して[0,7]の左半区間[0,3]から遍歴を開始する
[2,3]を[0,3]と比較し,状況bを満たすと,[0,3]の右半区間[2,3]から遍歴し,ちょうど重なることを発見し,ノード[2,3]countフィールドに1を加える.
II)対[4,5]は[0,7]の右半区間[4,7]から遍歴する.
[4,5]と[4,7]を比較し、状況bを満たし、[4,7]の左半区間[4,5]から遍歴し、ちょうど重なることを発見し、ノード[4,5]countフィールドに1を加算する
そこで[2,5]分割後の線分木の場合は図2
図2.分割[2,5]後の線分木の場合
明らかに,上記の遍歴動作の開始は[2,5]をセグメントツリーのセグメントに従って分割することであり,分割後の[2,3]と[4,5]は実際には[2,5]と完全に等価であることが分かった.
最後に、残りの2つの線分を同じ手順で分割した後、線分ツリーの場合は下図3のようになります.
このステップの時間的複雑度はO(N*log(MAX-MIN))である.
4.最後に、各値についてこの線分ツリーを巡り始めることができ、ノードのcountフィールドを加えると線分に現れる回数になります.
例えば4については、まず[0,7]を遍歴し、回数=0+1=1である.4右半区間で、遍歴[4,7]、回数=1+0=0;4は[4,7]左半区間で、回数=1+2=3である.4は[4,5]の左半分区間で、回数=3+0=4、遍歴終了、回数=3は4が3つの線分の中で現れたことを説明し、同じ理屈で他の値を求めることができ、このステップの時間複雑度はO(M*log(MAX-MIN))である.
最後に、総時間複雑度はO(N)+O(log(MAX-MIN)+O(N*log(MAX-MIN))+(M*log(MAX-MIN))=O((M+N)*log(MAX-MIN))である
log(MAX-MIX)<=64のため最後の時間複雑度はO(M+N)である
最後に、ソースを放出

#include 
using namespace std;
struct Line{
  int left, right, count;
  Line *leftChild, *rightChild;
  Line(int l, int r): left(l), right(r) {}
};

//        
void createTree(Line *root) {
  int left = root->left;
  int right = root->right;
  if (left < right) {
    int mid = (left + right) / 2;
    Line *lc =  new Line(left, mid);
    Line *rc =  new Line(mid + 1, right);
    root->leftChild = lc;
    root->rightChild = rc;
    createTree(lc);
    createTree(rc);
  }
}

//   [l, r]  
void insertLine(Line *root, int l, int r) {
  cout << l << " " << r << endl;
  cout << root->left << " " << root->right << endl << endl;
  if (l == root->left && r == root->right) {
    root->count += 1;
  } else if (l <= r) {
    int rmid = (root->left + root->right) / 2;
    if (r <= rmid) {
      insertLine(root->leftChild, l, r);
    } else if (l >= rmid + 1) {
      insertLine(root->rightChild, l, r);
    } else {
      int mid = (l + r) / 2;
      insertLine(root->leftChild, l, mid);
      insertLine(root->rightChild, mid + 1, r);
    }
  }
}
//      （   ）
void inOrder(Line* root) {
  if (root != NULL) {
    inOrder(root->leftChild);
    printf("[%d, %d], %d
", root->left, root->right, root->count);
    inOrder(root->rightChild);
  }
}

//   n         
int getCount(Line* root, int n) {
  int c = 0;
  if (root->left <= n&&n <= root->right)
    c += root->count;
  if (root->left == root->right)
    return c;
  int mid = (root->left + root->right) / 2;
  if (n <= mid)
    c += getCount(root->leftChild, n);
  else
    c += getCount(root->rightChild, n);
  return c;
}
int main() {
  int l[3] = {2, 4, 0};
  int r[3] = {5, 6, 7};
  int MIN = l[0];
  int MAX = r[0];
  for (int i = 1; i < 3; ++i) {
    if (MIN > l[i]) MIN = l[i];
    if (MAX < r[i]) MAX = r[i];
  }
  Line *root = new Line(MIN, MAX);
  createTree(root);
  for (int i = 0; i < 3; ++i) {
    insertLine(root, l[i], r[i]);
  }
  inOrder(root);
  int N;
  while (cin >> N) {
    cout << getCount(root, N) << endl;
  }
  return 0;
}