Zeitkomplexitätsnachweis für die Segmentbaumimplementierung des Bereichsummenproblems

Ich verstehe, dass Segmentbäume verwendet werden können, um die Summe der Unterarrays von . Und dass dies in Zeit gemäß dem Tutorial hier geschehen kann .$A$$\mathcal{O}(\log n)$

Ich kann jedoch nicht beweisen, dass die Abfragezeit tatsächlich . Dieser Link (und viele andere) besagen, dass wir beweisen können, dass auf jeder Ebene maximal Knoten verarbeitet werden und somit .$\mathcal{O}(\log n)$$4$$\mathcal{O}(4 \log n) = \mathcal{O}(\log n)$

Aber wie beweisen wir das, vielleicht durch Widerspruch?

Und wenn ja, wenn wir Segmentbäume für eine entfernte Summe höherdimensionaler Arrays verwenden würden, wie würde der Beweis erweitert werden?

Ich kann mir zum Beispiel vorstellen, eine Submatrixsumme zu finden, indem ich die ursprüngliche Matrix in 4 Quadranten (ähnlich wie Halbierungsintervalle in linearen Arrays) aufteile, um einen Quadranten-Segmentbaum zu erstellen, aber der Beweis entgeht mir.

Die Behauptung ist, dass es höchstens Knoten gibt, die auf jeder Ebene erweitert werden. Wir werden dies durch Widerspruch beweisen.$2$

Betrachten Sie den unten angegebenen Segmentbaum.

Angenommen, in diesem Baum werden Knoten erweitert. Dies bedeutet, dass der Bereich vom am weitesten links liegenden farbigen Knoten bis zum am weitesten rechts liegenden farbigen Knoten reicht. Beachten Sie jedoch, dass der gesamte Bereich des mittleren Knotens abgedeckt ist, wenn sich der Bereich bis zum Knoten ganz rechts erstreckt. Somit gibt dieser Knoten den Wert sofort zurück und wird nicht erweitert. Somit beweisen wir, dass wir auf jeder Ebene höchstens Knoten erweitern. Da es Ebenen gibt, sind die Knoten, die erweitert werden,$3$$2$$\log{n}$$\boxed{2 \cdot \log{n} = \Theta\left( {\log{n}} \right)}$