Präfixsummen und laufende Summen
Erstellen Sie Präfixsummen-Arrays, um Bereichssummen in O(1) zu beantworten, und wenden Sie die Technik auf Teilarrayprobleme wie das Teilarray mit maximaler Summe an.
Präfixsummen und laufende Summen ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Bereichssummenproblem
Bei einem Array nums sollen Sie viele Abfragen der Form beantworten: Wie groß ist die Summe der Elemente vom Index i bis zum Index j? Die naive Berechnung jeder Abfrage benötigt O(n) Zeit, sodass k Abfragen O(n×k) kosten. Mit einem Präfixsummen-Array berechnen Sie in O(n) eine laufende Summe und beantworten anschließend jede Abfrage in O(1). Dies ist eine der am häufigsten verwendeten Vorberechnungstechniken bei Interviews.
# 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 operationsDas Präfixsummen-Array aufbauen
Definieren Sie prefix[i] als die Summe von nums[0] bis einschließlich nums[i-1] (ein zusätzlicher Platz; ein nullbasierter Offset von 1 macht Randfälle übersichtlicher). Bauen Sie das Array in O(n) mit einem Durchlauf auf: prefix[i] = prefix[i-1] + nums[i-1]. Dann wird eine Bereichsabfrage sum(i, j) zu prefix[j+1] - prefix[i]: eine einzige Subtraktion mit Kosten von 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)) # 15Teilarraysumme gleich K
Die Anzahl der Teilarrays mit einer Summe gleich k zu ermitteln, ist ein klassisches Problem aus der Kombination von Hashmap und Präfixsumme. Die entscheidende Erkenntnis lautet: Die Summe des Teilarrays von i bis j ist gleich prefix[j] - prefix[i-1]. Soll dieser Wert k entsprechen, gilt prefix[i-1] = prefix[j] - k. Beim Durchlauf von links nach rechts mit einer laufenden Präfixsumme ermitteln wir, wie oft current_sum - k zuvor aufgetreten ist, und zählen so alle gültigen Teilarrays insgesamt in 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])Maximale Teilarraysumme mit Präfixsummen
Die maximale Teilarraysumme lässt sich als Präfixsummenproblem formulieren: Für jeden Index j möchten wir prefix[j] - prefix[i] über alle i < j maximieren. Das optimale i für jedes j ist die kleinste bisher gesehene Präfixsumme. Ein Durchlauf von links nach rechts, bei dem Sie min_prefix verfolgen, benötigt O(n) Zeit. Dies entspricht dem Kadane-Algorithmus, betrachtet durch die Perspektive der Präfixsummen.
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]))
# -12D-Präfixsummen für Rasterabfragen
Präfixsummen lassen sich auf zweidimensionale Raster erweitern. Definieren Sie P[i][j] als die Summe aller Elemente im Rechteck von (0,0) bis (i-1,j-1). Bauen Sie es mit der Formel der Ein- und Ausschlussrechnung auf: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. Jede Rechtecksumme von (r1,c1) bis (r2,c2) lässt sich anschließend mit vier Zugriffen in O(1) berechnen.
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 = 14Laufende Summe für den Gleichgewichtsindex
Der Gleichgewichtsindex ist die Position, an der die Summe der Elemente links davon gleich der Summe rechts davon ist. Berechnen Sie zunächst die Gesamtsumme und durchlaufen Sie dann das Array von links, während Sie eine laufende linke Summe führen. Die rechte Summe ist total - left_sum - nums[i]. Prüfen Sie die Gleichheit für jeden Index in O(1), was insgesamt O(n) ergibt. Dies zeigt, wie eine laufende Summe zwei separate Präfixsummen-Arrays ersetzt.
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])) # -1Produktarray ohne eigenes Element
Bei einem gegebenen Array sollen Sie ein Array zurückgeben, in dem jedes Element das Produkt aller anderen Elemente ist. Division ist nicht erlaubt. Verwenden Sie ein Präfixprodukt und ein Suffixprodukt: result[i] = (Produkt aller Elemente vor i) × (Produkt aller Elemente nach i). Erzeugen Sie die Präfixprodukte in einem Durchlauf von links nach rechts und multiplizieren Sie anschließend in einem Durchlauf von rechts nach links die Suffixprodukte mithilfe einer laufenden Variablen ein – für das Suffix ist kein zusätzliches Array erforderlich.
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 spacePräfixsumme mit Modulo
Bei manchen Aufgaben soll die Anzahl der Teilarrays ermittelt werden, deren Summe durch k teilbar ist. Verwenden Sie Präfixsummen modulo k: Wenn prefix[j] % k == prefix[i] % k gilt, ist sum(i+1..j) durch k teilbar. Eine Hashmap, die beim Durchlauf jeden Restwert zählt, ermöglicht O(n) Zeit. Entscheidend ist die Initialisierung freq[0] = 1, damit Teilarrays berücksichtigt werden, die bei Index 0 beginnen.
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)Differenzarray für Bereichsaktualisierungen
Ein Differenzarray ist das Gegenstück zu einer Präfixsumme. Berechnen Sie für ein gegebenes Array zunächst diff[i] = nums[i] - nums[i-1]. Das Addieren von x zu einem Bereich [l, r] erfordert im Differenzarray nur zwei O(1)-Operationen: diff[l] += x und diff[r+1] -= x. Nach allen Aktualisierungen rekonstruieren Sie das Ergebnisarray mit einem einzigen Präfixsummen-Durchlauf. Dadurch werden k Bereichsaktualisierungen von O(n×k) auf O(n + k) reduziert.
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]Präfixsummen in Interviewproblemen
Präfixsummen kommen in vielen Aufgabenkategorien vor:
- Bereichsabfragen — Teilarraysumme, Rechtecksumme
- Teilarray-Zählung — Summe gleich k, durch k teilbar
- Produktprobleme — Produkt ohne eigenes Element
- Gleichgewicht — Pivot-Index finden
- Bereichsaktualisierungen — Differenzarray
# 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)) # 3Laufende Summe und laufendes Maximum
Über Präfixsummen hinaus verwenden viele Aufgaben ein laufendes Maximum oder laufendes Minimum, das mit einer einzigen Variablen verwaltet wird. Das Muster Best-time-to-buy-stock verwendet einen laufenden Mindestpreis; beim Auffangen von Regenwasser von links wird eine laufende maximale Höhe verwendet. Diese Muster benötigen nur einen Durchlauf und O(1) zusätzlichen Speicherplatz und gelten daher als Maßstab für Effizienz bei Zeit und Speicher.
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])) # 5Schnelltest
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Präfixsummen verwandeln Bereichsabfragen mit O(n) in O(1)-Zugriffe, indem sie kumulative Summen in einem einzigen O(n)-Durchlauf vorberechnen, die Kombination von Präfixsummen und einer Hashmap ermöglicht O(n)-Lösungen zum Zählen von Teilarrays mit einer bestimmten Summe oder Teilbarkeitseigenschaft und Differenzarrays sind das Gegenstück: Sie ermöglichen Bereichsaktualisierungen in O(1) mit einem einzigen Präfixsummen-Durchlauf zur Rekonstruktion am Ende. Als Nächstes behandeln wir die Zwei-Zeiger-Technik, beginnend mit Zeigern an entgegengesetzten Enden.
Lerne Python mit einem KI-Tutor — kostenlos
Schreibe und führe echten Code in deinem Browser aus, bekomme sofortige Hilfe von einem 24/7 KI-Tutor und setze dein Lernen im Web oder in der App fort.
- Kurse
- 30
- Lektionen
- 120
Häufig gestellte Fragen
Ist die Lektion „Präfixsummen und laufende Summen“ kostenlos?
Ja — der vollständige Text von „Präfixsummen und laufende Summen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Präfixsummen und laufende Summen“?
Erstellen Sie Präfixsummen-Arrays, um Bereichssummen in O(1) zu beantworten, und wenden Sie die Technik auf Teilarrayprobleme wie das Teilarray mit maximaler Summe an. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Präfixsummen und laufende Summen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Array-Grundlagen und In-Place-Operationen
- Präfixsummen und laufende Summen
- Zwei Zeiger: entgegengesetzte Enden
- Zwei Zeiger: langsam und schnell