Proszę opisać jak zmodyfikować drzewa czerwono-czarne (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). Pozostałe operacje na powstałym drzewie powinny mieć złożoność taką samą jak w standardowym drzewie czerwono-czarnym. (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 ;)