区間 くかん 木 き インターバル木 き （英 えい Interval tree ）は、区間 くかん 保持 ほじ 木 き 構造 こうぞう データ構造 こうぞう の一種 いっしゅ 計算 けいさん 幾何 きか 学 がく アルゴリズム 。特 とく 指定 してい 区間 くかん 点 てん 全 すべ 区間 くかん 探 さが 問題 もんだい 効率 こうりつ 的 てき 解 と 例 たと 表示 ひょうじ 地図 ちず 内 ない 見 み 全 すべ 道路 どうろ 求 もと 次元 じげん 見 み 全 すべ 求 もと 用途 ようと 使 つか 似 に 区分 くぶん 木 き 英 えい Segment tree , segtree別物 べつもの
単純 たんじゅん 区間 くかん 互 たが 単純 たんじゅん 分木 ぶんぎ 表 あらわ 時間 じかん n ) となる。しかし、区間 くかん 同士 どうし 始点 してん 場合 ばあい 終点 しゅうてん 場合 ばあい 順序 じゅんじょ 異 こと 挿入 そうにゅう 時 じ 区間 くかん 比較 ひかく 問題 もんだい 素朴 そぼく 方法 ほうほう 同時 どうじ 木 き 作 つく 一方 いっぽう 始点 してん 一方 いっぽう 終点 しゅうてん 使 つか 行 おこな 木 き n ) の時間 じかん 可能 かのう 性 せい 区間 くかん 結果 けっか 必要 ひつよう n ) の時間 じかん 対 たい n + log n ) = O(n ) の時間 じかん 力 ちから 探索 たんさく 比較 ひかく 全 まった 改善 かいぜん
区間 くかん 木 き 問題 もんだい 解決 かいけつ 以下 いか 種類 しゅるい 設計 せっけい 解説 かいせつ
クエリにかかる時間 じかん n + m ) となる（n は格納 かくのう 区間 くかん 総数 そうすう m は報告 ほうこく 結果 けっか 総数 そうすう 構築 こうちく n log n ) の時間 じかん 使用 しよう 量 りょう n ) となる。
数 かず 直線 ちょくせん 上 じょう n 個 こ 区間 くかん 表 あらわ 構造 こうぞう 構築 こうちく 別 べつ 点 てん 区間 くかん 全 すべ 区間 くかん 効率 こうりつ 的 てき 検索 けんさく
まず、全 すべ 区間 くかん 含 ふく 範囲 はんい 特定 とくてい 中央 ちゅうおう x_center で分割 ぶんかつ x_center で分割 ぶんかつ 木 き 構造 こうぞう 平衡 へいこう 区間 くかん 種類 しゅるい 分類 ぶんるい x_center の左側 ひだりがわ 区間 くかん 群 ぐん S_left 、x_center の右側 みぎがわ 区間 くかん 群 ぐん S_right 、x_center にオーバーラップする区間 くかん 群 ぐん S_center とする。
S_left と S_right に属 ぞく 区間 くかん 群 ぐん 同様 どうよう 方式 ほうしき 再帰 さいき 的 てき 分割 ぶんかつ 左右 さゆう 区間 くかん 全 まった 残 のこ 状態 じょうたい
S_center に属 ぞく 区間 くかん 群 ぐん 中央 ちゅうおう 点 てん 区間 くかん 群 ぐん 区間 くかん 木内 きなし 別 べつ 構造 こうぞう 格納 かくのう 構造 こうぞう 構成 こうせい 区間 くかん 群 ぐん 始点 してん 区間 くかん 群 ぐん 終点 しゅうてん
結果 けっか 構築 こうちく 分木 ぶんぎ 以下 いか 格納 かくのう
中央 ちゅうおう 点 てん 位置 いち 区間 くかん 全体 ぜんたい 中央 ちゅうおう 点 てん 左側 ひだりがわ 区間 くかん 群 ぐん 対応 たいおう 区間 くかん 全体 ぜんたい 中央 ちゅうおう 点 てん 右側 みぎがわ 区間 くかん 群 ぐん 対応 たいおう 中心 ちゅうしん 点 てん 全 ぜん 区間 くかん 始点 してん 中心 ちゅうしん 点 てん 全 ぜん 区間 くかん 終点 しゅうてん 以上 いじょう 構築 こうちく 構造 こうぞう 区間 くかん 点 てん 与 あた 入力 にゅうりょく 全 すべ 区間 くかん 集合 しゅうごう 返 かえ
区間 くかん R が入力 にゅうりょく 与 あた 点 てん 入力 にゅうりょく 与 あた 場合 ばあい 還元 かんげん 始点 してん 終点 しゅうてん R の区間 くかん 内 ない 区間 くかん 全 すべ 探 さが 次元 じげん 場合 ばあい 各 かく 区間 くかん 始点 してん 終点 しゅうてん 構成 こうせい 単純 たんじゅん 木 き 構造 こうぞう 使 つか 各 かく 点 てん 対応 たいおう 区間 くかん 付与 ふよ
この O(log n ) の探索 たんさく 考慮 こうりょ 最小 さいしょう 最大 さいだい 点 てん 明 あき 範囲 はんい 内 ない 各 かく 点 てん 区間 くかん 対応 たいおう 区間 くかん 解 かい 加 くわ 始点 してん 終点 しゅうてん R に含 ふく 区間 くかん 考 かんが 二 に 重 じゅう 登録 とうろく 注意 ちゅうい 必要 ひつよう 防 ふせ 各 かく 区間 くかん 表 あらわ 構造 こうぞう 用意 ようい 解 かい 加 くわ 立 た
以上 いじょう 考慮 こうりょ 区間 くかん R が完全 かんぜん 含 ふく 区間 くかん 始点 してん 終点 しゅうてん R の中 なか 区間 くかん 探 さが R 内 うち 任意 にんい 点 てん 下記 かき 示 しめ 点 てん 実施 じっし 二 に 重 じゅう 登録 とうろく 注意 ちゅうい 必要 ひつよう
次 つぎ 点 てん x が入力 にゅうりょく 与 あた 場合 ばあい 考 かんが 通常 つうじょう 分木 ぶんぎ 走査 そうさ 同様 どうよう 再帰 さいき 的 てき 木 き 構造 こうぞう 走査 そうさ 各 かく x とそのノードの中央 ちゅうおう 点 てん x_center を比較 ひかく x が x_center より小 ちい 場合 ばあい 左側 ひだりがわ S_left を調 しら x が x_center よりも大 おお 場合 ばあい 右側 みぎがわ S_right を調 しら
根 ね 葉 は 走査 そうさ 過程 かてい S_center に含 ふく 区間 くかん 群 ぐん 処理 しょり x が x_center より小 ちい 場合 ばあい S_center にある区間 くかん 必 かなら 終点 しゅうてん x より大 おお x_center とオーバーラップできない）。したがって、S_center にある区間 くかん 群 ぐん x より始点 してん 小 ちい 区間 くかん 探 さが S_center に対応 たいおう 構造 こうぞう 使 つか 場合 ばあい 始点 してん 見 み 始点 してん 調 しら 始点 してん x より小 ちい 区間 くかん 必 かなら x を含 ふく 終点 しゅうてん x_center より大 おお x_center は x より大 おお 始点 してん 先頭 せんとう 順 じゅん 見 み 始点 してん x より小 ちい 出力 しゅつりょく 加 くわ 始点 してん x を超 こ 時点 じてん 終了 しゅうりょう
同様 どうよう x が x_center より大 おお 場合 ばあい S_center にある区間 くかん 群 ぐん 全 すべ 始点 してん x より小 ちい 終点 しゅうてん 使 つか 終点 しゅうてん x より大 おお 区間 くかん 探 さが
x が x_center と同一 どういつ 場合 ばあい S_center にある区間 くかん 群 ぐん 全 すべ 解 かい 含 ふく 以降 いこう 木 き 構造 こうぞう 走査 そうさ 必要 ひつよう
区間 くかん 木 き 高次 こうじ N 次元 じげん 拡張 かくちょう 時間 じかん 構築 こうちく 時間 じかん 次元 じげん 同 おな 使用 しよう 量 りょう n log n ) となる。
まず、N 次元 じげん 領域 りょういき 探索 たんさく 木 き 構築 こうちく 領域 りょういき R に始点 してん 終点 しゅうてん 含 ふく 全 すべ 区間 くかん 効率 こうりつ 的 てき 検索 けんさく 領域 りょういき 明 あき 残 のこ 問題 もんだい 領域 りょういき 内包 ないほう 領域 りょういき 探 さが 方法 ほうほう 探 さが N 次元 じげん 区間 くかん 木 き 構築 こうちく 座標軸 ざひょうじく R と交差 こうさ 調 しら 例 たと 次元 じげん 場合 ばあい 軸 じく 区間 くかん 木 き 構築 こうちく 四角形 しかっけい 領域 りょういき R がクエリとして与 あた 同時 どうじ 軸 じく 区間 くかん 木 き 対 たい 同様 どうよう 処理 しょり
次元 じげん 対応 たいおう 区間 くかん 木 き 余分 よぶん 必要 ひつよう 木 き 構造 こうぞう 走査 そうさ 際 さい 探 さが x と S_center の比較 ひかく 行 おこな 次元 じげん 場合 ばあい 使 つか 部分 ぶぶん 領域 りょういき 探索 たんさく 木 き 構築 こうちく S_center と領域 りょういき R のオーバーラップを効率 こうりつ 的 てき 検索 けんさく
別 べつ 手法 しゅほう Introduction to Algorithms, Second Edition [ 1] 章 しょう 章 しょう 記述 きじゅつ
挿入 そうにゅう 削除 さくじょ 時間 じかん n ) である（n は区間 くかん 総数 そうすう
これは、単純 たんじゅん 順序 じゅんじょ 木 き 例 たと 2分 ふん 探索 たんさく 木 き や平衡 へいこう 分 ふん 探索 たんさく 木 き 使 つか 順序 じゅんじょ 各 かく 区間 くかん 始点 してん 下限 かげん 値 ね 従 したが 各 かく 区間 くかん 終点 しゅうてん 上限 じょうげん 配下 はいか 部分 ぶぶん 木 き 全体 ぜんたい 最大 さいだい 上限 じょうげん 値 ち 格納 かくのう 情報 じょうほう 挿入 そうにゅう 削除 さくじょ 際 さい 保 たも h ) ステップ（h はそのノードの高 たか 処理 しょり 行 おこな 上位 じょうい 対 たい 最大 さいだい 値 ち 更新 こうしん
2つの区間 くかん A と B がオーバーラップするのは、A .low ≤ B .high と A .high ≥ B .low が同時 どうじ 成 な 立 た 場合 ばあい 木 き 構造 こうぞう 探 さが 走査 そうさ 場合 ばあい 以下 いか 場合 ばあい 即座 そくざ 除外 じょがい
右 みぎ 子 こ 始点 してん 下限 かげん 終点 しゅうてん 上限 じょうげん 大 おお 場合 ばあい 以降 いこう 部分 ぶぶん 木 き 走査 そうさ 必要 ひつよう 最大 さいだい 上限 じょうげん 値 ち 始点 してん 小 ちい 部分 ぶぶん 木 き 走査 そうさ 必要 ひつよう 区間 くかん 全体 ぜんたい 始点 してん 値 ね 次 つ 終点 しゅうてん 値 ね 順序 じゅんじょ 付 づ 利用 りよう 区間 くかん 二 に 重 じゅう 登録 とうろく 防 ふせ 区間 くかん 挿入 そうにゅう n ) だが、二 に 重 じゅう 登録 とうろく 検出 けんしゅつ k + log n ) がかかる（k は新 あら 区間 くかん 区間 くかん 数 すう
この木 き 構造 こうぞう 高 こう 次元 じげん 拡張 かくちょう 木 き 各 かく 対応 たいおう 次元 じげん 周期 しゅうき 的 てき 変化 へんか 例 たと 次元 じげん 場合 ばあい 奇数 きすう 軸 じく 範囲 はんい 扱 あつか 偶数 ぐうすう 軸 じく 扱 あつか 木 き 構造 こうぞう 木 き 回転 かいてん 平衡 へいこう 保 たも 明 あき
^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest , and Clifford Stein. Introduction to Algorithms , Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7
Mark de Berg; Marc van Kreveld; Mark Overmars; Otfried Schwarzkopf (2000). “Section 10.1: Interval Trees”. Computational Geometry (Second Revised ed.). Springer-Verlag. pp. 212-217. (centered interval tree). ISBN 3642096816 . NCID BA45765321 (日本語 にほんご 訳 やく M.ドパーグ、M.ファン.クリベルト、M.オーバマーズ、O.シュワルツコップ「10.1:区間 くかん 木 き 区間 くかん 木 き 計算 けいさん 幾何 きか 学 がく 応用 おうよう 近代 きんだい 科学 かがく 社 しゃ 年 ねん 原著 げんちょ 年 ねん 頁 ぺーじ ISBN 4764903881 。 Franco P. Preparata; Michael Ian Shamos (1985). Computational Geometry: An Introduction . augmented tree. Springer-Verlag. ISBN 0387961313 . NCID BA00039338 . ISBN 3540961313
