Why does a range query on a segment tree return at most ceil(log_2 N) nodes?

Question

If an array A[1..N] is represented using a segment tree having sets in each interval, why does a range query [L..R] returns at most ceil(log_2 N) sets (or disjoint intervals)?

If came across this statement while reading this answer.

To quote:

Find a disjoint coverage of the query range using the standard segment tree query procedure. We get O(logn) disjoint nodes, the union of whose multisets is exactly the multiset of values in the query range. Let's call those multisets s_1, ..., s_m (with m <= ceil(log_2 n)).

I tried searching for a proof, but couldn't find it on any site. Can anyone help me prove it?

Answer 1

Each node represents some power of 2^n elements where n is the height of the node. The segment tree never uses 2 neighboring nodes, because then if it can use two neighbors it will use their parent. Also, because ranges are continuous it will never use 2 nodes in one layer and some node that is below that layer and represents some range in between these 2 nodes. Therefore on each layer, there will be selected at most 2 nodes. Segment tree is made up of O(log n) layers, therefore, each query uses O(log n) nodes.

EDIT 1:

The actual bound of cell(log_2 N) is incorrect, and here is one of the examples: In this picture there is a segment tree for an array of length 8. If we make a query [1,6] (zero-based indexes) it will use 4 vertices (they are black on the image), and 4 > ceil(log_2(8)) = 3