<p>Let $p$ be the query point, and assume the interval tree is sorted by lower endpoint and each node stores the maximum endpoint in its subtree.</p>

<p>Perform a tree-walk and stop the recursion whenever the lower endpoint of the current node is greater than $p$, or the maximum is smaller than $p$.
Now at most one downward path (of length $O(\log n)$) reports no interval, namely the path that would be taken by binary searching the lowest endpoints for $p$.</p>

<p><strong>Illustrated example:</strong><br>
<img src="https://i.sstatic.net/QmC99.png" alt="interval tree">
Consider this interval tree and query point, the rightmost path visited by the pruned tree-walk is the path of orange nodes (which may not contain a reported interval if their maximum endpoints are all less than $p$).
All intervals in the right subtrees have a minimum endpoint greater than $p$ so can be ignored.
However, all intervals in left subtrees (red) of this path have minimum endpoint at most $p$. This means we are sure to report an interval for each (red) subtree (and subtrees thereof) whose maximum endpoint (over the entire subtree) is at least $p$.</p>

<p>Then, whenever we report a subsequent interval, we do so within $O(\log n)$ time.
Since there are $m$ such intervals, this amounts to $O((m+1)\log n)$ time.
Because we prune a tree-walk we also have an upper bound of $O(n)$ time.
This reduces to $O(n)\cap O((m+1)\log n)=O(\min(n,(m+1)\log n))$ time.</p>

CC BY-SA 3.0
2015-07-15T19:24:38.277Z
But if m=n, then this will give a lookup complexity of O(n log n), which cannot be the case since tree traversal is O(n)
user1715122
CC BY-SA 3.0
2015-07-15T22:46:24.467Z
Could you elaborate on the answer you have posted? Specifically, the part related to "at most one downward path.." and how that translates to O(min(n,(m+1)logn))?
user1715122
CC BY-SA 3.0
2015-07-17T06:33:36.240Z
@user1715122: I updated my answer.
Tim
CC BY-SA 3.0
2015-07-14T23:13:29.320Z
2015-07-16T10:44:46.383Z
2015-07-16T10:44:46.383Z
Tim
<p>If we consider the following problem: 
Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree (<a href="https://en.wikipedia.org/wiki/Interval_tree" rel="nofollow">Interval tree</a>). At some point in time later, we get a point, 
and are asked to return all intervals covering that point.</p>

<p>What is the complexity of the above lookup operation?</p>

<p>PS : This is not a homework question, but was an interview question.</p>

CC BY-SA 3.0
2015-07-09T20:50:40.003Z
Are you interested in the amortized complexity? Did they tell you if they want the total cost, was it clear whether the cost of building the data structure had to be included? In either case, the answer to the question your posing is in the [link](https://en.wikipedia.org/wiki/Interval_tree) you have included. I am guessing there was some space limitation you forgot to add or some other extra parameter?
Konstantinos Koiliaris
CC BY-SA 3.0
2015-07-10T02:53:51.310Z
No, that link doesn't give the lookup complexity for ALL intervals intersecting a given point for the augmented version of the interval tree.
user1715122
<cc.complexity-theory><ds.algorithms><online-algorithms>
Lookup complexity in augmented interval tree
user34725
# Lookup complexity in augmented interval tree

(Asked by: username_0 on 2015-07-09)

If we consider the following problem:
Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree ([Interval tree](https://en.wikipedia.org/wiki/Interval_tree)). At some point in time later, we get a point,
and are asked to return all intervals covering that point.

What is the complexity of the above lookup operation?

PS : This is not a homework question, but was an interview question.

**Tags:** cc.complexity-theory, ds.algorithms, online-algorithms
> **Comments:**
> **username_1**: Are you interested in the amortized complexity? Did they tell you if they want the total cost, was it clear whether the cost of building the data structure had to be included? In either case, the answer to the question your posing is in the [link](https://en.wikipedia.org/wiki/Interval_tree) you have included. I am guessing there was some space limitation you forgot to add or some other extra parameter?  
> **username_2**: No, that link doesn't give the lookup complexity for ALL intervals intersecting a given point for the augmented version of the interval tree.  

---

## 1 answers

### Answer by username_3 on 2015-07-14. Score: 2

Let $p$ be the query point, and assume the interval tree is sorted by lower endpoint and each node stores the maximum endpoint in its subtree.

Perform a tree-walk and stop the recursion whenever the lower endpoint of the current node is greater than $p$, or the maximum is smaller than $p$.
Now at most one downward path (of length $O(\log n)$) reports no interval, namely the path that would be taken by binary searching the lowest endpoints for $p$.

**Illustrated example:**  
![interval tree](https://i.sstatic.net/QmC99.png)
Consider this interval tree and query point, the rightmost path visited by the pruned tree-walk is the path of orange nodes (which may not contain a reported interval if their maximum endpoints are all less than $p$).
All intervals in the right subtrees have a minimum endpoint greater than $p$ so can be ignored.
However, all intervals in left subtrees (red) of this path have minimum endpoint at most $p$. This means we are sure to report an interval for each (red) subtree (and subtrees thereof) whose maximum endpoint (over the entire subtree) is at least $p$.

Then, whenever we report a subsequent interval, we do so within $O(\log n)$ time.
Since there are $m$ such intervals, this amounts to $O((m+1)\log n)$ time.
Because we prune a tree-walk we also have an upper bound of $O(n)$ time.
This reduces to $O(n)\cap O((m+1)\log n)=O(\min(n,(m+1)\log n))$ time.

> **Comments:**
> **username_2**: But if m=n, then this will give a lookup complexity of O(n log n), which cannot be the case since tree traversal is O(n)  
> **username_2**: Could you elaborate on the answer you have posted? Specifically, the part related to "at most one downward path.." and how that translates to O(min(n,(m+1)logn))?  
> **username_3**: @user1715122: I updated my answer.  

---

