10
$\begingroup$

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.

$\endgroup$
  • $\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
11
$\begingroup$

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 | |
$\endgroup$
-1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – greybeard Oct 4 at 8:23

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.