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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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, and the optional `goal` query parameter:

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

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

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.