# Why does a range query on a segment tree return at most $\lceil \log_2{N} \rceil$ nodes?

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

To quote:

Find a disjoint coverage of the query range using the standard segment tree query procedure. We get $$O(\log n)$$ disjoint nodes, the union of whose multisets is exactly the multiset of values in the query range. Let's call those multisets $$s_1, \dots, s_m$$ (with $$m \le \lceil \log_2 n \rceil$$).

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

• Does Wikipedia help? en.wikipedia.org/wiki/Segment_tree#Query May 2, 2020 at 9:28
• @YuvalFilmus I couldn't relate to querying procedure mentioned in Wikipedia. It queries on the intervals containing a given point. May 2, 2020 at 10:06

Here's the basic idea.

Let a dyadic interval be an interval of the form $$[2^b a,2^b(a+1)-1]$$ for some integer $$a,b \geq 0$$.

Claim 1. If $$m < 2^n$$ then any interval of the form $$[0,m-1]$$ can be written as the disjoint union of at most $$n$$ dyadic intervals.

Proof. Expand $$m$$ as a sum of decreasing powers of 2: $$m = 2^{a_1} + \cdots + 2^{a_k}.$$ Then we can write $$[0,m-1] = [0,2^{a_1}-1] \cup [2^{a_1},2^{a_1}+2^{a_2}-1] \cup \cdots \cup [2^{a_1} + \cdots + 2^{a_{k-1}},2^{a_1} + \cdots + 2^{a_k}-1].$$

Claim 2. If $$0 \leq m_1 \leq m_2 \leq 2^n$$ then any interval of the form $$[m_1,m_2-1]$$ can be written as the disjoint union of at most $$2n$$ dyadic intervals.

Proof. The binary expansion of $$m_1$$ and $$m_2$$ is of the form $$m_1 = x0y, m_2 = x1z$$, where $$|y|=|z|$$. Let $$m = x10^{|z|}$$. Using Claim 1, we can express $$[0,m_2-m-1]$$ as a union of at most $$n$$ dyadic intervals. Shifting these by $$m$$, we express $$[m,m_2-1]$$ as a union of at most $$n$$ dyadic intervals. Similarly, using Claim 1 we can express $$[0,m-m_1-1]$$ as a union of at most $$n$$ dyadic intervals. Shifting and inverting, we express $$[m_1,m-1]$$ as a union of at most $$n$$ dyadic intervals.

(In both cases, one needs to check that shifting, and possibly inverting, preservers an interval being dyadic.)

• Is it necessary for $m_1$ and $m_2$ to have a $0$ or a $1$ in their binary expansion? Won't that be restricting the choices for $m_1$ and $m_2$? May 3, 2020 at 5:57
• You might have to zero-extend them. May 3, 2020 at 6:25
• For example, if $m_1 = 7$ and $m_2 = 10$, then you should write $m_1 = 0111$ and $m_2 = 1010$. May 3, 2020 at 7:06