worst case running time of segment tree

Question

How is the range sum in segment tree O(logn) worst case?? Shouldn't it be O(n)? What if during the range sum operation,we traverse down both the left and right nodes as per the algorithm?

Answer 1

Lets call an active node a node that stores an interval that is neither completely included in the interval nor completely covered by the interval. It is easy to spot that there are at most 2 active nodes on each level for the traverse. Now if a node is not active you do not need to recurse in it - if the interval is completely covered add the value written in the node, if the interval does not intersect with the one we are interested in simply skip it. Thus the number of operations the algorithm will perform will be in the order of the levels of the tree or O(log(n)).

Answer 2

In the first step, you might have to traverse down both the left and right nodes, but in each subsequent step you will only have to traverse down one of the sides. Another way of seeing it is to note that if you want to find sum(n, m) (let's say this denotes the sum over the half-open interval [n, m)), we can compute it as

sum(n, m) = sum(0, m) - sum(0, n)

You'll notice that computing sum(0, n) and sum(0, m) each take logarithmic time, because again you don't need to traverse down both ways. For example,

sum(0, 13) = sum(0, 8) + sum(8, 12) + sum(12, 13)

where each of the terms on the right hand side is already stored in the segment tree.