領域木

【りょういきぎ (range tree)】

領域探索をサポートするデータ構造. 平面上の与えられた$n$点の集合$S$に対して, $x,y$軸に平行な質問長方形$Q$が与えられたとき, $Q$に含まれる$S$の点を列挙する問題に用いられる. 平面上の点集合の領域を$x$座標の中央値に基づいて二分割を繰り返し, その分割に対応する二分木を作る. さらに各ノードには対応する対象領域内にある点をすべて記憶しておく. これを領域木という. すると, $x,y$軸に平行な質問長方形$Q$が与えられたとき, %$Q$の$x$区間が互いに共通部分をもたない区間の和集合として表現されるが, その区間に対応するノードで1次元の探索をすることで$Q$に含まれる$S$の点を効率的に列挙できる.