Tworzenie tablicy sum prefiksowych
Jednorazowe wstępne obliczanie sum narastających
Tworzenie tablicy sum prefiksowych to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Problem wielokrotnych sum
Proszę wyobrazić sobie setki zapytań o sumę przedziału w jednej tablicy. Obliczanie każdej sumy od początku jest powolne. Rozwiązaniem jest suma prefiksowa. 🚀
Czym jest suma prefiksowa
Tablica sum prefiksowych przechowuje na każdym indeksie sumę wszystkich elementów aż do tego miejsca. Jedno wstępne przejście zamienia powolne obliczenia sum na natychmiastowe odpowiedzi.
Mały przykład
Dla [3, 1, 4] sumy narastające wynoszą kolejno 3, 4 i 8. Ta rosnąca lista sum jest właśnie sumą prefiksową.
Podstawowa rekurencja
Każdy element jest równy poprzedniej sumie powiększonej o bieżący element. Ta jednolinijkowa rekurencja jest sercem całej techniki.
prefix[i] = prefix[i - 1] + a[i]Budowanie w kodzie
Należy raz przejść przez tablicę, przechowując sumę narastającą. W każdym kroku dopisywana jest nowa suma, więc budowanie tablicy jest pojedynczym liniowym przejściem.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Dlaczego początkowe zero pomaga
Rozpoczęcie tablicy prefix od początkowego zera oznacza, że prefix[i] przechowuje sumę pierwszych i elementów. Dzięki temu późniejsze obliczenia dla przedziałów są przejrzyste.
Konwencja indeksowania
Przy zerze na początku prefix[k] jest równe a[0] + ... + a[k-1]. Zachowanie tej konwencji zapobiega uciążliwym błędom o jeden.
Koszt budowania
Budowanie tablicy sum prefiksowych dotyka każdego elementu dokładnie raz, więc kosztuje O(n) czasu. Ten koszt ponosi się raz, a następnie można korzystać z wyniku wielokrotnie.
Jedno przygotowanie, wiele zapytań
Największą korzyścią jest ten kompromis: jedno liniowe przejście na początku sprawia, że każde późniejsze zapytanie o sumę staje się szybkim odczytem zamiast wykonywania pętli.
Skrót w stylu Pythona
Biblioteka standardowa może zbudować sumy za Państwa. itertools.accumulate zwraca sumy narastające w jednym przejrzystym wywołaniu.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Należy uważać na pamięć
Tablica sum prefiksowych ma taką samą długość jak dane wejściowe powiększoną o jeden. W przypadku ogromnych danych należy pamiętać, że podwaja to zajętość pamięci.
Szybkie sprawdzenie
Budują Państwo tablicę sum prefiksowych. Co zwykle przechowuje indeks 0?
Podsumowanie
Nauczyli się Państwo budować tablicę sum prefiksowych w jednym przejściu O(n), z początkowym zerem ułatwiającym indeksowanie. Należy przygotować ją raz, a następnie używać wielokrotnie. ✅
Często zadawane pytania
Czy lekcja „Tworzenie tablicy sum prefiksowych” jest bezpłatna?
Tak — pełny tekst „Tworzenie tablicy sum prefiksowych” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Tworzenie tablicy sum prefiksowych”?
Jednorazowe wstępne obliczanie sum narastających Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Tworzenie tablicy sum prefiksowych”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Tworzenie tablicy sum prefiksowych
- Sumowanie dowolnego zakresu przez odejmowanie
- Zliczanie podtablic o zadanej sumie
- Tablice różnicowe do aktualizacji zakresów