Time Complexity proof for Segment Tree implementation of the ranged sum problem

Question

I understand that segment trees can be used to find the sum of sub array of $A$. And that this can done in $\mathcal{O}(\log n)$ time according to the tutorial here.

However I'm not able to prove that the querying time is indeed $\mathcal{O}(\log n)$. This link (and many others) say that we can prove that at each level, the maximum number of nodes processed is 4ドル$ and so $\mathcal{O}(4 \log n) = \mathcal{O}(\log n)$.

But how do we prove this, perhaps by contradiction?

And if so, if we were to use segment trees for ranged sum of higher dimensional arrays, how would the proof be extended?

For example, I can think of finding a sub matrix sum by dividing the original matrix into 4 quadrants (similar to halving intervals in linear arrays) building a quadrant segment tree but the proof eludes me.

• Nurlan: building of segment tree is O(n), querying is O(log n) and updating is O(log N). Its benefit over sum array is on its update complexity.

Answer 1

The claim is that there are at most 2ドル$ nodes which are expanded at each level. We will prove this by contradiction.

Consider the segment tree given below.

Segment Tree

Let's say that there are 3ドル$ nodes that are expanded in this tree. This means that the range is from the left most colored node to the right most colored node. But notice that if the range extends to the right most node, then the full range of the middle node is covered. Thus, this node will immediately return the value and won't be expanded. Thus, we prove that at each level, we expand at most $ 2 $ nodes and since there are $ \log{n} $ levels, the nodes that are expanded are $ \boxed{2 \cdot \log{n} = \Theta\left( {\log{n}} \right)} $

• student010101: If you copy and paste someone's answer, you should at least cit eit.

Answer 2

At each level (L) of tree there would be at max 2 nodes which could have partial overlap. (If unable to prove - why ?, please mention)

So, at level (L+1) we have to explore at max 4 nodes. and total height/levels in the tree is O(log(N)) (where N is number of nodes). Hence time complexity is O(4*Log(N)) ~ O(Log(N)).

PS: Please refer my answer on - Segment tree time complexity analysis

• greybeard: If unable to guess [why] At each level (L) of tree there would be at max 2 nodes which could have partial overlap.. The question being how do we prove [that at each level, the maximum number of nodes processed is 4], perhaps by contradiction?, it's not about guesswork. Moreover, adijo's 2015 answer depicts and argues this quite nicely. I don't see any insight this answer adds. I don't see any information the SO answer hyperlinked adds to what's presented in this answer.