> For the complete documentation index, see [llms.txt](https://cs2040s.devanshshah.dev/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs2040s.devanshshah.dev/orthogonal-range-queries.md).

# Orthogonal Range Queries

Example: Find the names of everyone aged between 22 and 27 (important in databases)

Firstly, you should be able to see how this is different from interval searching although in both the problems, there are points and intervals.

Moreover, this can be extended to d-dimensions (e.g. in the 2-D case, we would ask “find the points that lie within a given rectangle”, thus giving the name “orthogonal” range queries) but we only discuss the 1-D case here.

### Strategy

1. Use a Binary Search Tree in which all the nodes are sorted by the property we are going to query by. (Decide the underlying data structure)
2. Store all the points in the **leaves** of the tree. (Internal nodes only store copies of these) (**Invariant**: The tree would still have the BST property)
3. Each internal node `v` stores the **max of any leaf in its left subtree** (this is quite a common strategy to help you determine whether to go left or go right). (Augment the data structure to help you perform your operations)

<figure><img src="/files/Yp9TCMHtfpsAYBc4z8Lq" alt=""><figcaption></figcaption></figure>

### Algorithm

1. Find the split node (the highest node that falls between the interval bounds)
2. Perform `leftTraverasal`
3. Perform `rightTraversal`

Example of a left and right traversal:

<figure><img src="/files/0bbqhzdAXX3YJj2YwWOE" alt=""><figcaption></figcaption></figure>

<figure><img src="/files/0v78tENo5puvNz6gjSNw" alt=""><figcaption></figcaption></figure>

### Pseudocode

```java
findSplit(low, high)
	v = root;
	done = false;
	while !done {
		if (high <= v.key) v = v.left;
		else if (low > v.key) v = v.right;
		else (done = true)
	}
	return v;
```

```java
rightTraversal(v, low, high)
	if (v.key <= high)
		allLeafTraversal(v.left);              // basically do an in order traversal of all the leaves in that subtree
		rightTraversal(v.right, low, high);
	}
	else {
		rightTraversal(v.left, low, high);
	}
```

```java
leftTraversal(v, low, high)
	if (low <= v.key)
		allLeafTraversal(v.right); // basically do an in order traversal of all the leaves in that subtree
		leftTraversal(v.left, low, high);
	}
	else {
		leftTraversal(v.right, low, high);
	}
```

### Running Time Analysis

1. Finding split node: $$O(\log n)$$
2. `leftTraversal`
   1. Doing all leaf traversal takes $$O(k)$$ where k is the number of leaves in the subtree.
   2. Then, `leftTraversal` is recursively called (at most $$O(\log n)$$ times)
3. `rightTraversal` is identical (in running time) to `leftTraversal`

So, query time complexity is $$O(k + \log n)$$ where $$k$$ is the number of points found.

(Preprocessing) Building the entire tree takes $$O(n\log n)$$ time. - Run `QuickSelect` to find the median, then run `QuickSelect` on the two halves and so on.. at each level, it takes $$O(n)$$ time to run the `QuickSelect`.

Insertion, deletion takes $$O(\log n)$$ time.

Total space complexity $$O(n)$$ (Number of nodes in a tree $$\leq$$ $$2 \times$$ number of leaves in the tree) (easy to prove since $$1 + 2 + 4 + \dots + 2^n = 2^{n+1} - 1$$ and at every level of the tree, the maximum number of possible nodes double).