典型タグ

laminar区間族の包含木構築

互いに素または包含関係にある区間を端点順に走査し、stackで直接包含する親を定めてdummy root付き包含木を作り、点を最小包含区間へ対応させる。

この典型を扱う単元: laminar区間族の包含木構築

検索別名: interval containment tree、laminar family tree、laminar区間包含木、区間包含木

未知問からこの典型を見つける手掛かり

扱う対象
  • containment parent
  • dummy root
  • laminar intervals
  • opening and closing endpoints
使う手掛かり
  • 包含関係をqueryで再利用
  • 区間同士が非交差
  • 点を最小包含区間へ写す
保つ不変量
  • open intervals form one ancestor stack
  • stack top is direct parent
  • subtree equals containment
求めるもの
  • 包含木構築
  • 区間queryの木上path化
適用しない条件
  • 交差する一般区間のoverlap graph
  • 値の大小から作るCartesian tree
分類・前提・学習成果

分類と直接の前提

概念上の親: 木モデルと構造

    関連する典型

      学習成果と学習単位

      • laminar区間の開閉端点をstackで処理し、直接包含関係と各点の最小包含区間を木として構築して、包含差分を木上pathへ変換できる。

        laminar区間族の包含木構築で学ぶ

      代表問題

      この典型の考え方を具体的な問題で確かめるための入口です。

      関連問題

      この典型が主タグまたは補助タグとして付いている問題です。