Editing Interval tree (section)

===Searching for all overlapping intervals===
Let's use <math>a_q, b_q, m_q, d_q</math> for the query interval, and <math>M_n</math> for the key of a node (compared to <math>m_i</math> of intervals)

Starting with root node, in each node, first we check if it is possible that our query interval overlaps with the node subtree using minimum and maximum values of node (if it is not, we don't continue for this node).

Then we calculate <math>\min \left\{ d_i \right\}</math> for intervals inside this node (not its children) to overlap with query interval (knowing <math>m_i = M_n</math>):

<math>\min \left\{ d_i \right\} = \left| m_q - M_n \right| - d_q</math>

and perform a query on its binary heap for the <math>d_i</math>'s bigger than <math>\min \left\{ d_i \right\}</math>

Then we pass through both left and right children of the node, doing the same thing.

In the worst-case, we have to scan all nodes of the binary search tree, but since binary heap query is optimum, this is acceptable (a 2- dimensional problem can not be optimum in both dimensions)

This algorithm is expected to be faster than a traditional interval tree (augmented tree) for search operations. Adding elements is a little slower in practice, though the order of growth is the same.