Algorithms and Data Structures · Senior · Question 33 of 75

Which structure lets you find all intervals overlapping a point in O(log n + k)?

Explanation

An interval tree is a balanced BST ordered by start, where each node also stores the maximum end in its subtree, so whole branches can be skipped. Calendars and genome tools use it.

Further reading

Problem with a question

Algorithms and Data Structures · Senior · question 33

Test yourself

Take the Algorithms and Data Structures · Senior quiz: questions and options are shuffled, and you get a review of your mistakes at the end.

Take this quiz