Algorytmy i struktury danych · Senior · Pytanie 8 z 75
Kiedy wybrać drzewo przedziałowe zamiast drzewa Fenwicka?
- ✓Poprawna odpowiedź: Dla zapytań o min lub max na zakresie albo aktualizacji zakresów
- 2Gdy tablica nigdy się nie zmienia po utworzeniu
- 3Gdy pamięć musi być ściśle mniejsza niż n elementów
Wyjaśnienie
Drzewa Fenwicka pasują do operacji odwracalnych, takich jak sumy. Drzewo przedziałowe przechowuje agregat na każdy przedział i obsługuje dowolną operację łączną (min, max, nwd), a z leniwą propagacją także aktualizacje zakresów. Zajmuje od około 2n do 4n węzłów.