suma elementow w drzewie w podanym przedziale w O(logn)

Question

Proszę opisać jak zmodyfikować drzewa BST (przechowujące elementy typu int) tak, by operacja:
int sum(T, x, y)
obliczająca sumę elementów z drzewa o wartościach z przedziału [x, y] działała w czasie O(log n) (gdzie n to rozmiar drzewa T). (Podpowiedź: Warto w każdym węźle drzewa przechowywać pewną dodatkową informację, która upraszcza wykonanie operacji sum i którą można łatwo aktualizować).

Jakoś nie mam pomysłu jak zmodyfikować, myślałem, żeby trzymać dodatkowe pole, które zawiera sume poddrzewa łącznie z samym sobą, ale nie wiem jak później to liczyć.
Prosze o pomoc ;)

Answer 1

Pomysł jest z grubsza taki, aby właśnie trzymać w każdym węźle sumę w podrzewie.

I pseudokod wyglądałby mniej więcej tak:

wynik = suma wszystkich w wartości w całym drzewie
szukasz w drzewie x z tym, że idąc w prawo odejmujesz od wyniku sumę z lewego poddrzewa
następnie szukasz w drzewie y z tym, że idąc w lewo odejmujesz od wyniku sumę z prawego poddrzewa

Rozrysuj sobie jakiś przykład na kartce to zrozumiesz w pełni