Upper Bound for number of values returned in Segment Tree query

Revision en1, by ZeyadKhattab, 2020-02-12 13:29:26

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?

Tags #segment tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English ZeyadKhattab 2020-02-12 13:29:26 653 Initial revision (published)