Dowód złożoności czasu dla implementacji problemu segmentu dystansowego w drzewie segmentów

Rozumiem, że drzewa segmentów można wykorzystać do znalezienia sumy podgrupy $A$. I to można zrobić w$\mathcal{O}(\log n)$czas zgodnie z tutorialem tutaj .

Jednak nie jestem w stanie udowodnić, że czas na zapytanie jest rzeczywiście $\mathcal{O}(\log n)$. Ten link (i wiele innych) mówi, że możemy udowodnić, że na każdym poziomie maksymalna liczba przetworzonych węzłów wynosi$4$ a więc $\mathcal{O}(4 \log n) = \mathcal{O}(\log n)$.

Ale jak to udowodnić, być może przez sprzeczność?

A jeśli tak, jeśli mielibyśmy użyć drzew segmentowych do sumowania zasięgów tablic wyższych wymiarów, w jaki sposób dowód zostałby rozszerzony?

Na przykład mogę myśleć o znalezieniu sumy podmacierzy, dzieląc pierwotną macierz na 4 ćwiartki (podobne do połówek przedziałów w liniowych tablicach) budując drzewo segmentu kwadrantu, ale dowód mi umyka.

Twierdzi się, że są co najwyżej $2$węzły, które są rozwinięte na każdym poziomie. Udowodnimy to przez sprzeczność.

Rozważ poniższe drzewo segmentów.

Powiedzmy, że są $3$węzły, które są rozwinięte w tym drzewie. Oznacza to, że zakres jest od lewego najbardziej kolorowego węzła do prawego najbardziej kolorowego węzła. Zauważ jednak, że jeśli zakres rozciąga się na najbardziej prawy węzeł, wówczas pełny zakres środkowego węzła jest objęty. Zatem ten węzeł natychmiast zwróci wartość i nie zostanie rozwinięty. Udowadniamy zatem, że na każdym poziomie rozwijamy się co najwyżej$2$ węzły i ponieważ istnieją $\log{n}$ poziomy, rozwinięte są węzły $\boxed{2 \cdot \log{n} = \Theta\left( {\log{n}} \right)}$