A Recursive Approach to Segment Trees, Range Sum Queries & Lazy Propagation


@subham_pasari You are right! Good catch! Sorry about that.
Keep the feedback coming. I'll try to do a consolidated fix soon.

@kchida Ohh no! Don't worry. I definitely meant the Violin like instrument (Viola) and not the french expression (Voila). You see, I love string instruments! :P
Just kidding. I'll fix that soon. Thanks for pointing it out!

I think it is not trivial to see why the time complexity of query/read operation is O(logn), on stack overflow there is a good proof for that: http://stackoverflow.com/questions/27185066/segmenttreetimecomplexityanalysis

@adamlhh I thought I had made it clear that a read query would, at worst, traverse the entire depth of the tree. A balanced binary tree would have a depth logarithmic to the order of the input size.
Though, I must thank you for SO answer (and hence the lemma.) I have always, kind of, known about this result. Never felt the need to actually go ahead and prove it.
