Matematyka.pl

Słyszałem, że drzewo przedziałowe można zaimplementować z wykorzystaniem stl-a a dokładniej set-a. (zawsze to kilka linijek mniej kodu niż jak bym miał sam je implementować). Drzewo takie ma mieć dopuszczone dwie operacje: dodaj(klucz,wartość) oraz max_z_przedziału(a,b).
Proszę więc Was o pomoc lub jakiś link z implementacją takiego drzewa.

Z góry dziękuje za pomoc.

Kto Ci takich rzeczy naopowiadał . Niech się wstydzi. Takie drzewo implementuje się samemu na tablicy, co jest nawet kilka-(nascie) razy wydajniejsze niz typowe operacje na secie. Pomijam już tutaj fakt, że na secie się tego nie da zrobić, a nawet jeśli to nakład pracy nie będzie mniejszy niż pisanie własnego drzewa. W poszukiwaniu implementacji polecam przeszukać google, w szczególności po angielsku warto szukać "segment tree".

Na takim "gotowym" secie z STL faktycznie byłoby trudno.

Można by użyć drzewa czerwono-czarnego, czyli de facto napisać własnego seta, bardzo podobnego do tego z STL, który pozwalałby na dodatkową operację maksimum na przedziale. Ale jest to oczywiście znacznie bardziej pracochłonne.