Algorytmy i struktury danych · Middle · Pytanie 56 z 75
Jak wiele razy odpowiadać na „sumę elementów od i do j” w niezmiennej tablicy?
- 1Posortować tablicę i używać wyszukiwania binarnego na każde zapytanie
- ✓Poprawna odpowiedź: Raz policzyć sumy prefiksowe, potem
prefix[j + 1] - prefix[i]na zapytanie - 3Liczyć sumę pętlą od nowa dla każdego zapytania
Wyjaśnienie
Przygotowanie to O(n), a każde zapytanie O(1). Jeśli tablica zmienia się między zapytaniami, sumy prefiksowe przestają działać i potrzebne jest drzewo Fenwicka lub przedziałowe.