Algorytmy i struktury danych · Senior · Pytanie 7 z 75
Jaki problem rozwiązuje drzewo Fenwicka (binary indexed tree)?
- 1Sortowanie tablicy w miejscu w O(n)
- 2Najkrótsze ścieżki w drzewie z wagami
- ✓Poprawna odpowiedź: Sumy prefiksowe z aktualizacjami, obie w O(log n)
Wyjaśnienie
Zwykłe sumy prefiksowe dają zapytania w O(1), ale aktualizacje w O(n). Drzewo Fenwicka równoważy oba w O(log n), używając najmłodszego ustawionego bitu indeksu (i & -i) do skoków między zakresami.