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.

  • $\begingroup$ 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. $\endgroup$ – Nurlan Oct 19 '17 at 5:22

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)} $

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.