# Running time analysis of a segment tree

Can someone provide an analysis of the update and query operations of a segment tree?

I thought of a way which goes like this - At every node, we make at most two recursive calls on the left and right sub-trees. If we could prove that one of these calls terminates fairly quickly, the time complexity would be logarithmically bounded. But how do we prove this?

• Actually in the case of querying you choose whether to go left or right based on the range covered. Look at the implementation details in the topcoder example you linked to below. – 1110101001 Nov 29 '14 at 4:49
• In some case you go both left and right. That's why I'm finding it hard to prove the claim – adijo Nov 30 '14 at 4:47
• Yes, fair point. After some intense googling I think I found the answer you are looking for and even addresses this conundrum: web.stanford.edu/class/cs166/lectures/00/Extra00.pdf – 1110101001 Nov 30 '14 at 6:37
• Thanks, but how exactly does the "flush against the wall" structure ensure a log n complexity? They haven't elaborated on that part. – adijo Dec 3 '14 at 5:28