search

chaimleib / intervaltree

A mutable, self-balancing interval tree. Queries may be by point, by range overlap, or by range containment.
Apache License 2.0
636 stars 108 forks source link

Find interval min, max efficiently #110

Open cmpute opened 3 years ago

cmpute commented 3 years ago

Is there any efficient way to query the min/max value at given position in the intervaltree? The only method I'm aware of to find the min/max value is like max(tree[point]). Ideally a better way is to trace the min/max value in each node while updating the tree, which is O(log n) instead of O(n). Is this feasible in the library?

chaimleib commented 3 years ago

O(log n) is better than O(n).

If you are aiming for O(1) time for each insertion and O(1) for the final query, that is possible, but best solved with a different data structure than this interval tree.

cmpute commented 3 years ago

Thanks for the reply. I meant that, the current possible best time is O(log n) for insertion but O(n) for min/max query (you have to iterate over the query results). If we add tracking of min/max value for subtree in each node, then the min/max query could be O(1) while the overhead for insertion is very small.