Sumowanie dowolnego zakresu przez odejmowanie
Odpowiadanie na zapytania range[l..r] w stałym czasie
Sumowanie dowolnego zakresu przez odejmowanie to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 2 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.
Rzeczywista korzyść
Zbudowanie tablicy sum prefiksowych było przygotowaniem. Teraz następuje najważniejsza część: obliczanie sumy dowolnego przedziału za pomocą pojedynczego odejmowania. ⚡
Podstawowa idea
Suma przedziału to po prostu jedna duża suma pomniejszona o mniejszą sumę. Odjęcie dwóch wartości sum prefiksowych przejrzyście usuwa wszystko spoza rozpatrywanego przedziału.
Wzór
Aby obliczyć sumę elementów od l do r, należy odjąć prefix[l] od prefix[r + 1]. Ten jeden wzór działa dla każdego zakresu.
range_sum = prefix[r + 1] - prefix[l]Dlaczego to działa
prefix[r + 1] zawiera wszystkie elementy aż do r, a prefix[l] zawiera wszystkie elementy przed l. Różnica pozostawia dokładnie środkowy fragment.
Przykład z rozwiązaniem
Dla [3, 1, 4] suma prefiksowa wynosi [0, 3, 4, 8]. Aby obliczyć sumę elementów o indeksach od 1 do 2, należy odjąć 3 od 8, co daje 5. To zgadza się z sumą 1 i 4.
Zapytania w stałym czasie
Każde zapytanie wymaga tylko jednego odejmowania, więc działa w czasie O(1). Tysiąc zapytań kosztuje tyle samo na zapytanie co jedno.
Uwaga na przesunięcie o jeden
Najczęstszy błąd dotyczy indeksu na prawym końcu. Przy początkowym zerze zawsze należy używać prefix[r + 1], a nie prefix[r]. Należy pilnować tej granicy.
Włącznie czy wyłącznie
Już na początku należy zdecydować, czy r należy do zakresu. Ten wzór traktuje zakres jako domknięty, czyli obejmujący zarówno l, jak i r, czego oczekuje większość zadań konkursowych.
Opakowanie w funkcję
Niewielka funkcja pomocnicza sprawia, że kod pozostaje czytelny, a indeksy są obsługiwane w jednym miejscu. Zamiast wpisywać obliczenia bezpośrednio, warto użyć tego narzędzia pomocniczego.
def query(l, r):
return prefix[r + 1] - prefix[l]Obsługa całej tablicy
Aby obliczyć sumę całej tablicy, należy ustawić l równe 0, a r równe n minus 1. Wzór zwróci prefix[n], czyli sumę całkowitą.
Gdzie to rozwiązanie jest szczególnie przydatne
Za każdym razem, gdy zadanie zawiera wiele zapytań o sumę zakresu w niezmiennej tablicy, sumy prefiksowe zastępują pętlę O(n) dla każdego zapytania natychmiastowymi odpowiedziami.
Szybki sprawdzian
Należy obliczyć sumę elementów o indeksach od l do r włącznie.
Podsumowanie
Można teraz obliczyć sumę dowolnego zakresu w czasie O(1), odejmując prefix[l] od prefix[r + 1]. Należy pamiętać o przesunięciu wynikającym z początkowego zera, a kod będzie wolny od błędów. ✅
Często zadawane pytania
Czy lekcja „Sumowanie dowolnego zakresu przez odejmowanie” jest bezpłatna?
Tak — pełny tekst „Sumowanie dowolnego zakresu przez odejmowanie” 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 „Sumowanie dowolnego zakresu przez odejmowanie”?
Odpowiadanie na zapytania range[l..r] w stałym czasie Ć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 2 z 4.
Ile czasu zajmuje lekcja „Sumowanie dowolnego zakresu przez odejmowanie”?
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