1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – DoubtExpert May 3 at 5:57
  • $\begingroup$ You might have to zero-extend them. $\endgroup$ – Yuval Filmus May 3 at 6:25
  • $\begingroup$ For example, if $m_1 = 7$ and $m_2 = 10$, then you should write $m_1 = 0111$ and $m_2 = 1010$. $\endgroup$ – Yuval Filmus May 3 at 7:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.