Editing Interval tree (section)

=== Membership queries ===
Some performance may be gained if the tree avoids unnecessary traversals. These can occur when adding intervals that already exist or removing intervals that don't exist.

A total order can be defined on the intervals by ordering them first by their lower bounds and then by their upper bounds. Then, a membership check can be performed in <math>O(\log n)</math> time, versus the <math>O(k + \log n)</math> time required to find duplicates if <math>k</math> intervals overlap the interval to be inserted or removed. This solution has the advantage of not requiring any additional structures. The change is strictly algorithmic. The disadvantage is that membership queries take <math>O(\log n)</math> time.

Alternately, at the rate of <math>O(n)</math> memory, membership queries in expected constant time can be implemented with a hash table, updated in lockstep with the interval tree. This may not necessarily double the total memory requirement, if the intervals are stored by reference rather than by value.