Range Tree Search
Range Tree Search Range tree search answers orthogonal range queries over points in multiple dimensions. It extends balanced binary search trees by storing secondary structures at each node. For two dimensions, each node in the primary tree stores a secondary tree over the remaining coordinate. Problem Given a set of points $(x, y)$ and a query rectangle: $$ [x_1, x_2] \times [y_1, y_2] $$ return all points such that: $$...