# 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:

$$
x_1 \le x \le x_2 \quad \text{and} \quad y_1 \le y \le y_2
$$

## Structure

A 2D range tree consists of:

| level               | structure                               |
| ------------------- | --------------------------------------- |
| primary tree        | balanced BST on x coordinate            |
| secondary structure | BST on y coordinates stored per subtree |

Each node stores all points in its subtree sorted by y.

## Algorithm

First, locate the canonical decomposition of the x range in the primary tree. Then query each associated secondary structure.

```text id="rt0k8q"
range_tree_search(node, x1, x2, y1, y2, result):
    if node is null:
        return

    if node.x is fully inside [x1, x2]:
        report_all(node.secondary_tree, y1, y2, result)
        return

    if x1 <= node.x:
        range_tree_search(node.left, x1, x2, y1, y2, result)

    if node.x <= x2:
        range_tree_search(node.right, x1, x2, y1, y2, result)
```

Secondary query:

```text id="rt1m6v"
report_all(tree, y1, y2, result):
    if tree is null:
        return

    if tree.node.y in [y1, y2]:
        add all matching points in subtree
```

## Example

Points:

| point  |
| ------ |
| (2, 3) |
| (4, 7) |
| (5, 1) |
| (7, 6) |
| (8, 2) |

Query:

$$
[3, 7] \times [1, 5]
$$

Matches:

| point  | inside |
| ------ | ------ |
| (5, 1) | yes    |
| (7, 6) | no     |
| (4, 7) | no     |

Result:

$$
{(5, 1)}
$$

## Correctness

The primary tree partitions points by x coordinate. Any node whose subtree lies fully inside the x range contributes all its points without further filtering.

For partially covered nodes, recursion ensures all relevant subtrees are explored.

The secondary structure guarantees that only points with y values in the query range are reported.

Since every point is stored in exactly one subtree per level and is checked against both x and y constraints, all and only valid points are returned.

## Complexity

Let $n$ be number of points and $k$ number of reported points.

| dimension | time              |
| --------- | ----------------- |
| 2D query  | $O(\log^2 n + k)$ |

Space complexity:

$$
O(n \log n)
$$

due to secondary structures.

## When to Use

Range trees are useful when:

* multidimensional orthogonal range queries are needed
* data is static or semi static
* query performance is more important than update cost
* computational geometry problems are involved

Compared to k d trees, range trees provide more predictable worst case bounds but require more memory.

## Implementation

```python id="rt2n7x"
class Node:
    def __init__(self, x):
        self.x = x
        self.left = None
        self.right = None
        self.secondary = []  # sorted by y
        self.points = []

def report_all_secondary(points, y1, y2, result):
    for p in points:
        if y1 <= p[1] <= y2:
            result.append(p)

def range_tree_search(node, x1, x2, y1, y2, result):
    if node is None:
        return

    if x1 <= node.x <= x2:
        report_all_secondary(node.secondary, y1, y2, result)

    if x1 < node.x:
        range_tree_search(node.left, x1, x2, y1, y2, result)

    if node.x < x2:
        range_tree_search(node.right, x1, x2, y1, y2, result)
```

```go id="rt3m8v"
type Point struct {
	X int
	Y int
}

type Node struct {
	X        int
	Left     *Node
	Right    *Node
	Secondary []Point
}

func reportAll(points []Point, y1, y2 int, res *[]Point) {
	for _, p := range points {
		if p.Y >= y1 && p.Y <= y2 {
			*res = append(*res, p)
		}
	}
}

func RangeTreeSearch(node *Node, x1, x2, y1, y2 int, res *[]Point) {
	if node == nil {
		return
	}

	if node.X >= x1 && node.X <= x2 {
		reportAll(node.Secondary, y1, y2, res)
	}

	if x1 < node.X {
		RangeTreeSearch(node.Left, x1, x2, y1, y2, res)
	}

	if node.X < x2 {
		RangeTreeSearch(node.Right, x1, x2, y1, y2, res)
	}
}
```