区間木

【くかんぎ (interval tree)】

整数区間$I\,$を根に対応させ, 以下その区間をほぼ二等分しながら左右の子に対応させていきながら単位長さの区間の集合に分割する分割法を木構造のデータ構造で表現したもの. 区間木のノードにはそれぞれ分割に対応する整数区間が付随する. さらに$I\,$の与えられた部分区間の集合${\mathcal {I}}\,$をこの対応に基づいて適切に記憶することにより, 区間の集合に対する探索をサポートする効率的なデータ構造が得られる. それを用いれば, $n\,$個の区間の集合${\mathcal {I}}\,$に対して, 質問点$x\,$を含む ${\mathcal {I}}\,$ の区間をすべて求める問題などが区間木を用いて効率的に解ける.