Find interval min, max efficiently

[cmpute]

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]

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]

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.