Algorytmy i struktury danych · Junior · Pytanie 67 z 75
Czym jest tablica sum prefiksowych?
- 1Tablica pierwszych znaków każdego napisu
- ✓Poprawna odpowiedź: Element
ito suma pierwszychielementów - 3Oryginalna tablica posortowana raz rosnąco
Wyjaśnienie
Po jednym przejściu O(n) suma dowolnego zakresu [l, r) to prefix[r] - prefix[l], liczona w O(1). To podstawowy trik, gdy ta sama tablica jest wiele razy pytana o sumy zakresów.