Suppose that we have an array of size
n and we want to build an interval tree for all possible ranges that can be created inside this array. So in our leafs we have the ranges
, , , , ... , [n], and merging two of them together we end up having the root node holding the range
[0, n]. For example we have the following interval tree for an array of size 6.
The total amount of nodes is
I'm trying to understand what's the maximum posible
root - internal node paths that we need to make in order to answer a query on any range. I know that the total amount of nodes that we are going to visit for any query is in the order of
log n but I can't see why, which is the reason why I'm asking this question.
For example in the picture above, for the query
[1, 4] we will do the following visits:
[0,5] => [0,2] => [0,1] =>  => [0,1] => [0,2] =>  => [0,2] => [0,5] => [3,5] => [3,4] => [3,5] = > [0,5] => end
We have to travel from the root to some other internal node 3 times in total.
Now let's see a different example:
If our query is
[1, 8] we will have to do 4 root to some other internal node paths, so this doesn't look constant to me, it was 3 before, now it's 4.
So I can't understand why querying in an interval tree is
How can you formally prove that querying is indeed
O(log n), ie the amount of nodes that your algorithm must visit in order to answer any query is in the order of