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

Question

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)?

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(\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?

• Yuval Filmus: Does Wikipedia help? en.wikipedia.org/wiki/Segment_tree#Query
• DoubtExpert: @YuvalFilmus I couldn't relate to querying procedure mentioned in Wikipedia. It queries on the intervals containing a given point.

Answer 1

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 2ドルn$ 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.)

• DoubtExpert: 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$?
• Yuval Filmus: You might have to zero-extend them.
• Yuval Filmus: For example, if $m_1 = 7$ and $m_2 = 10,ドル then you should write $m_1 = 0111$ and $m_2 = 1010$.