Witam.
Mam takie zadanie do zrobienia:
Dane: M losowych liczb całkowitych nie większych niż 100, zapamiętanych w tablicy o indeksach 0..M-1, przedział [a,b], 0<=a,b<=M-1
Wynik: Obliczenie min na danym przedziale [a,b] na drzewie przedziałowym.
I nie do końca wiem, jak się za nie zabrać, głównie dlatego, że nie rozumiem idei drzewa przedziałowego. Próbowałem znaleźć jakiś dobry artykuł na ten temat w internecie, ale jest tego mało i tak średnio wytłumaczone.
Ktoś byłby w stanie objaśnić?
o_O ban na google, prawda?
http://was.zaa.mimuw.edu.pl/?q=node/9
Jak najbardziej to czytałem. Ale nie rozumiem teraz jak mam z tych losowych liczb utworzyć drzewo przedziałowe i jak znaleźć na nim minimum.
Korzen to przedzial 0..M-1, jego lewe dziecko to 0..M-1/2, prawe dziecko to M-1/2 +1 .. M-1, cos ci swita?
No świta. Ale M to jest ilość liczb czyli dla 8 wyjdzie tak jak na stronie którą podałeś.
Ale co ja mam zrobić z tymi wylosowanymi liczbami? One mają być zapisane jako wartości liści, czy co?
To zalezy od zadania, ale ja rozumiem ze operacje przedzialowe masz robic na "indeksach" a nie na wartosciach. Tzn masz znalezc minimum z liczb zawartych pomiedzy danymi indeksami.
Aaa dobra teraz mi się zgadza :D Dzięki wielkie, miałem problem z ogarnięciem tego, a nie pomyślałem, że tu chodzi o indeksy...