A Segment Tree query works by breaking down a segment that is queried into several pre-computed segment tree segments and merge them together to find the answer for the queried segment.
What is a tight upper bound for the number of segment tree segments that are merged together?
I believe it's $$$2*log(n)$$$ because the following scenario is possible:
4 nodes are visited in the majority of the segment tree levels, 2 of them make recursive calls, (visiting 4 more in the next level), and 2 segments are returned.
Is this analysis correct?
Is there a tighter upper bound?