# 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).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs2040s.devanshshah.dev/orthogonal-range-queries.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.