Sumy prefiksowe i sumy narastające
Zbudują Państwo tablice sum prefiksowych, aby odpowiadać na zapytania o sumę zakresu w O(1), a następnie zastosują tę technikę do problemów z podtablicami, takich jak podtablica o maksymalnej sumie.
Sumy prefiksowe i sumy narastające to bezpłatna lekcja DSA Interview Prep 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Problem sumy przedziału
Mając tablicę nums, należy odpowiadać na wiele zapytań postaci: jaka jest suma elementów od indeksu i do indeksu j? Naiwne obliczenie każdego zapytania zajmuje O(n), więc k zapytań kosztuje O(n×k). Dzięki tablicy sum prefiksowych można wstępnie obliczyć sumę bieżącą w O(n), a następnie odpowiadać na każde zapytanie w O(1). Jest to jedna z najczęściej używanych technik wstępnego obliczania podczas rozmów rekrutacyjnych.
# Naive: O(n) per query
def range_sum_naive(nums, i, j):
return sum(nums[i:j+1])
nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3)) # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4)) # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operationsBudowanie tablicy sum prefiksowych
Niech prefix[i] oznacza sumę elementów od nums[0] do nums[i-1] (jedno dodatkowe miejsce; przesunięcie indeksów o 1 przy indeksowaniu od zera upraszcza przypadki brzegowe). Tablicę należy zbudować w O(n) w jednym przejściu: prefix[i] = prefix[i-1] + nums[i-1]. Wtedy zapytanie o przedział sum(i, j) przyjmuje postać prefix[j+1] - prefix[i]: jest to pojedyncze odejmowanie zajmujące O(1).
def build_prefix(nums):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix, i, j):
return prefix[j+1] - prefix[i] # O(1)
nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre) # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3)) # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15 correct
print(range_sum(pre, 1, 3)) # 15Suma podtablicy równa K
Znalezienie liczby podtablic o sumie równej k to klasyczny problem wykorzystujący mapę haszującą i sumy prefiksowe. Kluczowa obserwacja: suma podtablicy od i do j jest równa prefix[j] - prefix[i-1]. Jeśli chcemy, aby była równa k, to prefix[i-1] = prefix[j] - k. Przesuwając się od lewej do prawej i utrzymując bieżącą sumę prefiksową, sprawdzamy, ile razy wcześniej wystąpiła wartość current_sum - k, zliczając wszystkie poprawne podtablice łącznie w czasie O(n).
from collections import defaultdict
def subarray_sum_k(nums, k):
count = 0
current = 0
freq = defaultdict(int)
freq[0] = 1 # empty prefix
for n in nums:
current += n
count += freq[current - k] # how many prior sums give diff=k
freq[current] += 1
return count
print(subarray_sum_k([1, 1, 1], 2)) # 2
print(subarray_sum_k([1, 2, 3], 3)) # 2 ([1,2] and [3])Maksymalna suma podtablicy z użyciem prefiksów
Maksymalną sumę podtablicy można sformułować jako problem sum prefiksowych: dla każdego indeksu j chcemy zmaksymalizować prefix[j] - prefix[i] dla wszystkich i < j. Najlepszym i dla danego j jest najmniejsza suma prefiksowa napotkana do tej pory. Przejście od lewej do prawej przy jednoczesnym śledzeniu min_prefix daje czas O(n). Jest to odpowiednik algorytmu Kadane’a postrzeganego z perspektywy sum prefiksowych.
def max_subarray_prefix(nums):
max_sum = float('-inf')
min_pre = 0 # prefix[0] = 0
current = 0
for n in nums:
current += n
max_sum = max(max_sum, current - min_pre)
min_pre = min(min_pre, current)
return max_sum
print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6 (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -1Dwuwymiarowe sumy prefiksowe dla zapytań o siatkę
Sumy prefiksowe można rozszerzyć na siatki 2D. Niech P[i][j] oznacza sumę wszystkich elementów w prostokącie od (0,0) do (i-1,j-1). Tablicę należy zbudować za pomocą wzoru włączeń i wyłączeń: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. Następnie na zapytanie o sumę dowolnego prostokąta od (r1,c1) do (r2,c2) można odpowiedzieć w O(1), korzystając z czterech odwołań.
def build_2d_prefix(grid):
R, C = len(grid), len(grid[0])
P = [[0]*(C+1) for _ in range(R+1)]
for r in range(1, R+1):
for c in range(1, C+1):
P[r][c] = (P[r-1][c] + P[r][c-1]
- P[r-1][c-1] + grid[r-1][c-1])
return P
def rect_sum(P, r1, c1, r2, c2):
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1)) # 3+0+5+6 = 14Suma bieżąca dla indeksu równowagi
Indeks równowagi to pozycja, w której suma elementów po lewej stronie jest równa sumie po prawej stronie. Najpierw należy obliczyć sumę całkowitą, a następnie przejść po tablicy, utrzymując bieżącą sumę lewej strony. Suma po prawej stronie to total - left_sum - nums[i]. Sprawdzanie równości dla każdego indeksu zajmuje O(1), co daje łącznie O(n). Pokazuje to, jak suma bieżąca zastępuje dwie oddzielne tablice sum prefiksowych.
def find_pivot_index(nums):
total = sum(nums)
left_sum = 0
for i, n in enumerate(nums):
# right_sum = total - left_sum - nums[i]
if left_sum == total - left_sum - n:
return i
left_sum += n
return -1
print(find_pivot_index([1, 7, 3, 6, 5, 6])) # 3
print(find_pivot_index([1, 2, 3])) # -1Tablica iloczynów bez własnego elementu
Mając tablicę, należy zwrócić tablicę, w której każdy element jest iloczynem wszystkich pozostałych elementów. Dzielenie jest niedozwolone. Należy użyć iloczynu prefiksowego i iloczynu sufiksowego: result[i] = (iloczyn wszystkich elementów przed i) × (iloczyn wszystkich elementów po i). Najpierw w jednym przejściu od lewej do prawej należy zbudować iloczyny prefiksowe, a następnie w jednym przejściu od prawej do lewej uwzględnić iloczyny sufiksowe, używając zmiennej przechowującej bieżący iloczyn — bez dodatkowej tablicy dla sufiksów.
def product_except_self(nums):
n = len(nums)
result = [1] * n
# Left pass: result[i] = product of nums[:i]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Right pass: multiply in product of nums[i+1:]
suffix = 1
for i in range(n-1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6] O(n) time, O(1) extra spaceSuma prefiksowa modulo
Niektóre zadania wymagają policzenia liczby podtablic, których suma jest podzielna przez k. Korzystając z sum prefiksowych modulo k: jeśli prefix[j] % k == prefix[i] % k, to sum(i+1..j) jest podzielne przez k. Mapa haszująca zliczająca każdą wartość reszty podczas przechodzenia po tablicy daje czas O(n). Kluczowa inicjalizacja to freq[0] = 1, aby uwzględnić podtablice zaczynające się od indeksu 0.
from collections import defaultdict
def subarray_div_by_k(nums, k):
freq = defaultdict(int)
freq[0] = 1
current = 0
count = 0
for n in nums:
current = (current + n) % k
count += freq[current]
freq[current] += 1
return count
print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7 (seven subarrays divisible by 5)Tablica różnicowa do aktualizacji przedziałów
Tablica różnicowa jest odwrotnością sumy prefiksowej. Mając tablicę, należy wstępnie obliczyć diff[i] = nums[i] - nums[i-1]. Dodanie x do przedziału [l, r] wymaga tylko dwóch operacji O(1) na tablicy różnicowej: diff[l] += x i diff[r+1] -= x. Po wykonaniu wszystkich aktualizacji należy odtworzyć tablicę wynikową w jednym przejściu, obliczając sumy prefiksowe. Zmienia to koszt k aktualizacji przedziałów z O(n×k) na O(n + k).
def apply_range_updates(n, updates):
# updates: list of (l, r, val)
diff = [0] * (n + 1)
for l, r, val in updates:
diff[l] += val
diff[r+1] -= val
# Reconstruct with prefix sum
result = []
running = 0
for i in range(n):
running += diff[i]
result.append(running)
return result
# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]Suma prefiksowa w zadaniach rekrutacyjnych
Sumy prefiksowe pojawiają się w wielu kategoriach zadań:
- Zapytania o przedziały — suma podtablicy, suma prostokąta
- Zliczanie podtablic — suma równa k, podzielność przez k
- Problemy iloczynowe — iloczyn bez własnego elementu
- Równowaga — znajdowanie indeksu pivota
- Aktualizacje przedziałów — tablica różnicowa
# Template: prefix sum + hash map for subarray problems
from collections import defaultdict
def subarray_count_template(nums, target):
"""
Count subarrays with property involving prefix sums.
Adapt 'target' and lookup condition for each problem.
"""
freq = defaultdict(int)
freq[0] = 1 # empty prefix at sum=0
current = 0
count = 0
for n in nums:
current += n
count += freq[current - target] # adjust per problem
freq[current] += 1
return count
print(subarray_count_template([1,2,3,2,1], 3)) # 3Suma bieżąca i maksimum bieżące
Poza sumami prefiksowymi w wielu zadaniach wykorzystuje się maksimum bieżące lub minimum bieżące, utrzymywane w jednej zmiennej. Problem najlepszego momentu zakupu akcji wykorzystuje bieżącą minimalną cenę, a obliczanie ilości zatrzymanej wody deszczowej od lewej strony — bieżącą maksymalną wysokość po lewej. Wzorce te wymagają tylko jednego przejścia i O(1) dodatkowej pamięci, co czyni je złotym standardem zarówno pod względem czasu, jak i pamięci.
def max_profit(prices):
# Running minimum buy price
min_price = float('inf')
max_prof = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_prof:
max_prof = price - min_price
return max_prof
def left_max_array(heights):
# Running max from left for trapping rain water
n = len(heights)
left_max = [0] * n
left_max[0] = heights[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], heights[i])
return left_max
print(max_profit([7,1,5,3,6,4])) # 5Szybki sprawdzian
Proszę sprawdzić swoją znajomość pojęć Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji omówiono: sumy prefiksowe przekształcają zapytania o przedziały, które zajmują O(n), w odwołania O(1) dzięki wstępnemu obliczeniu sum skumulowanych w jednym przejściu O(n), połączenie sum prefiksowych z mapą haszującą umożliwia rozwiązania O(n) zadań polegających na zliczaniu podtablic o określonej sumie lub podzielności oraz tablice różnicowe są odwrotnością sum prefiksowych: umożliwiają aktualizacje przedziałów w O(1), a na końcu wymagają tylko jednego przejścia z sumami prefiksowymi w celu odtworzenia wyniku. Następnie zajmiemy się techniką dwóch wskaźników, zaczynając od wskaźników ustawionych na przeciwnych końcach.
Często zadawane pytania
Czy lekcja „Sumy prefiksowe i sumy narastające” jest bezpłatna?
Tak — pełny tekst „Sumy prefiksowe i sumy narastające” 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Sumy prefiksowe i sumy narastające”?
Zbudują Państwo tablice sum prefiksowych, aby odpowiadać na zapytania o sumę zakresu w O(1), a następnie zastosują tę technikę do problemów z podtablicami, takich jak podtablica o maksymalnej sumie. Ćwiczysz DSA Interview Prep 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ąć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep 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 „Sumy prefiksowe i sumy narastające”?
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 DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep 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
- Podstawy tablic i operacje w miejscu
- Sumy prefiksowe i sumy narastające
- Dwa wskaźniki: przeciwległe końce
- Dwa wskaźniki: wolny i szybki