Por que uma consulta de intervalo em uma árvore de segmento retorna na maioria dos nós $ \ lceil \ log_2 {n} \ rceil $?

Question

Se uma matriz $ a [1 \ ldots n] $ é representado usando uma árvore de segmento com conjuntos em cada intervalo, por que uma consulta de intervalo $ [l \ l \ ldots r] $ retorna no máximo $ \ lceil \ log_2 {n} \ rceil $ conjuntos (ou disjunto intervalos)?

Se se deparar com esta declaração durante a leitura esta resposta .

para citar:

.

Encontre uma cobertura desonesta da linha de consulta usando o segmento padrão Procedimento de consulta de árvore. Recebemos $ o (\ log n) $ nós disjuntos, a união de Cujos multissets são exatamente o multisset de valores na faixa de consulta. Vamos chamar os multisets $ s_1, \ DOTS, S_M $ (com $ m \ le \ lceil \ log_2 n \ rceil $ ).

Eu tentei procurar por uma prova, mas não consegui encontrá-lo em qualquer site. Alguém pode me ajudar a provar isso?

Answer 1

Aqui está a ideia básica.

Deixe um intervalo dyadic ser um intervalo do formulário $$ [2 ^ B a, 2 ^ B (A + 1) -1] $$ Para algum inteiro $ a, b \ Geq 0 $ .

reivindicação 1. se $ m <2 ^ n $ então qualquer intervalo da forma $ [0, m-1] $ pode ser escrito como a união disjunta de no máximo $ n $ intervalos diádicos.

prova. Expandir $ M $ como uma soma de poderes decrescentes de 2: $$ m= 2 ^ {a_1} + \ CDOts + 2 ^ {a_k}. $$ Então podemos escrever $$ [0, m-1]= [0,2 ^ {a_1} -1] \ copo [2 ^ {a_1}, 2 ^ {a_1} + 2 ^ {a_2} -1] \ cope \ cdoz \ copo [2 ^ {a_1} + \ cdoz + 2 ^ {a_ {k-1}}, 2 ^ {a_1} + \ cdoz + 2 ^ {a_k} -1]. $$

reivindicação 2. se $ 0 \ leq m_1 \ leq m_2 \ leq 2 ^ n $ então qualquer intervalo da forma $ [m_1, m_2-1] $ pode ser escrito como a união disjunta de no máximo $ 2N $ intervalos diádicos.

prova. a expansão binária da $ m_1 $ e $ m_2 $ é da forma $ m_1= x0y, m_2= x1z $ , onde $ | y |= | z | $ < / span>. Deixe $ m= x10 ^ {| z |} $ . Usando a reivindicação 1, podemos expressar $ [0, m_2-m-1] $ como uma união de no máximo $ n $ intervalos diádicos. Mudando estes por $ m $ , nós expressamos $ [m, m_2-1] $ como uma união de No máximo $ n $ intervalos diádicos. Da mesma forma, usando a reivindicação 1 Podemos expressar $ [0, m-m_1-1] $ como uma união de no máximo $ n $ intervalos diádicos. Mudando e invertendo, expressamos $ [m_1, m-1] $ como uma união de no máximo $ n $ Intervalos Dyadic.

(Em ambos os casos, é preciso verificar essa mudança, e possivelmente invertendo, preservadores um intervalo sendo dídico.)