¿Por qué una consulta de rango en un árbol de segmento regresa a la mayoría de los nodos $ \ lceil \ log_2 {n} \ rceil $?

Question

Si una matriz $ a [1 \ ldots n] $ se representa utilizando un árbol de segmento que tiene conjuntos en cada intervalo, ¿por qué la consulta de rango $ [LDOTS R] $ devuelve a la mayoría $ \ lceil \ log_2 {n} \ rceil $ sets (o disjoint intervalos)?

Si se encuentra en esta declaración mientras lee esta respuesta .

para citar:

Encuentre una cobertura de disjoint del rango de consulta utilizando el segmento estándar Procedimiento de consulta de árbol. Obtenemos $ o (\ log n) $ nodos disjoint, la unión de Cuyos multisetos son exactamente el multiset de valores en el rango de consultas. Llamemos a los multisets $ s_1, \ puntos, s_m $ (con $ m \ le \ lceil \ log_2 n \ rceil \ log_2 n \ rceil $ ).

Intenté buscar una prueba, pero no pude encontrarlo en ningún sitio. ¿Alguien puede ayudarme a probarlo?

Answer 1

Aquí está la idea básica.

Determine un intervalo de Dyadic sea un intervalo de la forma $$ [2 ^ B A, 2 ^ B (A + 1) -1] $$ para algunos enteros $ a, b \ geq 0 $ .

la reivindicación 1. si $ m <2 ^ n $ luego cualquier intervalo del formulario $ [0, M-1] $ se puede escribir como la Unión de Disjoint de más $ n $ intervalos diádicos.

Prueba. expandir $ m $ como una suma de poderes decrecientes de 2: $$ M= 2 ^ {A_1} + \ CDOTS + 2 ^ {A_K}. $$ Entonces podemos escribir $$ [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]. $$

la reivindicación 2. si $ 0 \ leq m_1 \ leq m_2 \ leq 2 ^ n $ luego cualquier intervalo del formulario $ [M_1, M_2-1] $ se puede escribir como la unión de disjoint de más $ 2n $ intervalos diádicos.

Prueba. la expansión binaria de $ m_1 $ y $ m_2 $ es de la forma $ m_1= x0y, m_2= x1z $ , donde $ | y | | z | $ < / span>. Deje que $ m= x10 ^ {| z |} $ . Uso de la reivindicación 1, podemos expresar $ [0, m_2-m-1] $ como unión de más $ n $ intervalos diádicos. Cambiando estos por $ m $ , expresamos $ [M, M_2-1] $ como unión de A lo sumo $ n $ intervalos diádicos. Del mismo modo, utilizando la reivindicación 1 Podemos expresar $ [0, m-m_1-1] $ como unión de la mayoría de $ n $ intervalos diádicos. Desplazamiento e inversión, expresamos $ [M_1, M-1] $ como unión de más $ n $ Intervalos diádicos.

(En ambos casos, uno necesita verificar que cambie el cambio, y posiblemente invirtiendo, preserva un intervalo que sea dyadic.)