Warum ist eine Reichweite auf einem Segmentbaum in den meisten $ \ lceil \ log_2 {n} \ RCEIL $ NODES zurück?

Question

Wenn ein Array $ a [1 \ ldots n] $ mit einem Segmentstaum mit Sätzen in jedem Intervall dargestellt wird, warum ist eine Reichweiteabfrage $ [l \ ldots r] $ gibt auf den meisten $ \ lceil \ log_2 {n} \ RCEIL $ sets (oder discoint Intervalle)?

falls auf dieser Aussage kam, während Sie diese Antwort .

an Zitat:

Finden Sie eine disjunkte Abdeckung des Abfragebereichs mit dem Standardsegment Baumabfrageverfahren. Wir erhalten $ o (\ \ log n) $ disjunkte Knoten, die Union von Wessen Multisets ist genau das Multiset der Werte im Abfragebereich. Nennen wir diese Multisets $ s_1, \ dots, s_m $ (mit $ m \ le \ lceil \ log_2 n \ rceil $ ).

Ich habe versucht, nach einem Beweis zu suchen, konnte sie jedoch auf keiner Stelle finden. Kann mir jemand helfen, es zu beweisen?

Answer 1

Hier ist die Grundidee.

lass ein dyadic ein Intervall ein Intervall des Formulars sein $$ [2 ^ B A, 2 ^ B (A + 1) -1] $$ Für einige Ganzzahl $ A, B \ geq 0 $ .

Anspruch 1. Wenn $ M <2 ^ N $ dann ein beliebiges Intervall des Formulars $ [0, m-1] $ kann als disjunkte Union von höchstens $ n $ dyadic Intervalle schreiben.

Beweis. Erweitern $ M $ als Summe der abnehmenden Mächte von 2: $$ M= 2 ^ {A_1} + \ CDS + 2 ^ {a_k}. $$ Dann können wir schreiben $$ [0, m-1]= [0,2 ^ {a_1} -1] \ cup [2 ^ {a_1}, 2 ^ {a_1} + 2 ^ {a_2} -1] \ cup \ CDs \ Cup [2 ^ {A_1} + \ CDs + 2 ^ {A_ {K-1}}, 2 ^ {A_1} + \ CDs + 2 ^ {a_k} -1]. $$

Anspruch 2. Wenn $ 0 \ LEQ M_1 \ LEQ M_2 \ LEQ M_1 \ LEQ M_2 \ LEQ MAG 2 ^ N $ dann ein beliebiges Intervall des Formulars $ [M_1, M_2-1] $ kann als disjunkte Union von höchstens $ 2N $ dyadic Intervalle geschrieben werden.

Beweis. Die Binärausweitung von $ m_1 $ und $ m_2 $ hat das Formular $ m_1= x0y, m_2= x1z $ , wobei $ | y |= | Z | $ < / span>. Lassen Sie $ M= X10 ^ {| Z |} $ . Verwenden des Anspruchs 1, wir können $ [0, m_2-m-1] $ als Union von höchstens $ n ausdrücken $ dyadische Intervalle. Verschieben Sie diese mit $ M $ , wir drücken $ [m, m_2-1] $ als Union von höchstens $ n $ dyadische Intervalle. In ähnlicher Weise können wir mit Anspruch 1 ausdrücken $ [0, M-M_1-1] $ als Union von höchstens $ n $ dyadische Intervalle. Wir verschieben und invertieren, wir drücken $ [M_1, M-1] $ als Union von höchstens $ n $ dyadische Intervalle.

(In beiden Fällen muss man diese Verschiebung und möglicherweise invertierende Bediener ein Intervall dyadisch überprüfen.)