Perché una query della gamma su un albero di segmento ritorna al massimo $ \ lceil \ log_2 {n} \ rceil $ nodi?

Question

Se un array $ A [1 \ Ldots n] $ è rappresentato utilizzando un albero di segmento avente set di set in ciascun intervallo, perché una interrogativa intervallo $ [l \ ldots r] $ ritorna al massimo $ \ lceil \ log_2 {n} \ rceil $ set (o disgiunta Intervalli)?

Se è venuto in questa affermazione durante la lettura Questa risposta .

per citare:

.

Trova una copertura disgiunta della gamma di query utilizzando il segmento standard Procedura di query ad albero. Otteniamo $ o (\ log n) $ nodi disgiunti, l'unione di il cui multisets è esattamente il multiset di valori nel campo della query. Chiamiamo quei multisets $ s_1, \ dots, s_m $ (con $ m \ le \ lceil \ log_2 n \ rceil $ ).

Ho provato a cercare una prova, ma non riuscivo a trovarlo su nessun sito. Qualcuno può aiutarmi a dimostrarlo?

Answer 1

Ecco l'idea di base.

Lasciare un intervallo dyadic un intervallo del modulo $$ [2 ^ b A, 2 ^ B (A + 1) -1] $$ Per alcuni Integer $ a, b \ geq 0 $ .

rivendicazione 1. se $ m <2 ^ n $ quindi qualsiasi intervallo del modulo $ [0, M-1] $ può essere scritto come un'unione disgiunta al massimo $ N $ intervalli diadici.

Prova. Espandi $ M $ come somma dei poteri decrescenti di 2: $$ M= 2 ^ {A_1} + \ Cdots + 2 ^ {A_K}. $$ Quindi possiamo scrivere $$ [0, M-1]= [0,2 ^ {A_1} -1] \ Coppa [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]. $$

rivendicazione 2. se $ 0 \ leq m_1 \ leq m_2 \ leq 2 ^ n $ quindi qualsiasi intervallo del modulo $ [M_1, M_2-1] $ può essere scritto come un'unione disgiunta al massimo $ 2N $ Intervalli Dyadic.

Proof. L'espansione binaria di $ M_1 $ e $ m_2 $ è della forma $ M_1= x0y, m_2= x1z $ , dove $ | y |= | z | $ < / span>. Let $ m= x10 ^ {| z |} $ . Usando la rivendicazione 1, possiamo esprimere $ [0, m_2-m-1] $ come unione di al massimo $ n $ intervalli diadici. Spostandoli per $ M $ , expressiamo $ [m, m_2-1] $ come unione di al massimo $ N $ intervalli diadici. Allo stesso modo, utilizzando la rivendicazione 1 possiamo esprimere $ [0, m-m_1-1] $ come unione di al massimo $ N $ Intervalli Dyadic. Spostamento e invertente, esprimere $ [M_1, M-1] $ come unione di al massimo $ N $ Intervalli diadici.

(In entrambi i casi, è necessario controllare tale spostamento, e possibilmente invertendo, preservatori un intervallo di essere diadiato.)