Click here to see the full article post
In the function queryLazySegTree(), I think you wanted to call the same function recursively and not querySegTree().
@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/segment-tree-time-complexity-analysis
@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.
@1337c0d3r Link is not working. Kindly fix it.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.