[C++] Implementacja drzewa przedziałowego na secie

satre · Post autor: **satre** » 12 wrz 2011, o 23:37

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.

Zordon · Post autor: **Zordon** » 12 wrz 2011, o 23:59

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".

paladin · Post autor: **paladin** » 16 wrz 2011, o 19:17

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.