Somme prefisse e totali progressivi
Costruisca array di somme prefisse per rispondere in O(1) a query sulle somme di intervalli e applichi la tecnica a problemi su subarray, come il subarray a somma massima
Somme prefisse e totali progressivi è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Il problema della somma su un intervallo
Dato un array nums, è necessario rispondere a molte query del tipo: qual è la somma degli elementi dall'indice i all'indice j? Calcolare ogni query in modo ingenuo richiede tempo O(n), quindi k query costano O(n×k). Con un array delle somme prefisse, si precalcola un totale progressivo in O(n) e si risponde poi a ogni query in O(1). Questa è una delle tecniche di pre-calcolo più utilizzate nei colloqui tecnici.
# 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 operationsCostruire l'array delle somme prefisse
Definire prefix[i] come la somma da nums[0] a nums[i-1] (uno slot aggiuntivo; l'offset di 1 con indicizzazione da zero semplifica i casi ai bordi). Costruirlo in O(n) con un'unica scansione: prefix[i] = prefix[i-1] + nums[i-1]. A quel punto, una query sull'intervallo sum(i, j) diventa prefix[j+1] - prefix[i]: una sola sottrazione con costo 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)) # 15Somma del sottoarray uguale a K
Trovare il numero di sottoarray con somma uguale a k è un problema classico che combina hash map e somme prefisse. L'intuizione fondamentale è che la somma del sottoarray da i a j è uguale a prefix[j] - prefix[i-1]. Se si vuole che questa sia uguale a k, allora prefix[i-1] = prefix[j] - k. Scorrendo da sinistra a destra e mantenendo una somma prefissa progressiva, si cerca quante volte current_sum - k è comparso in precedenza, contando così tutti i sottoarray validi in tempo totale 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])Somma massima del sottoarray con somme prefisse
La somma massima di un sottoarray può essere formulata come un problema di somme prefisse: per ogni indice j, si vuole massimizzare prefix[j] - prefix[i] su tutti gli i < j. Il valore ottimale di i per ogni j è la somma prefissa minima osservata fino a quel momento. Una scansione da sinistra a destra che mantiene min_prefix richiede tempo O(n). È equivalente all'algoritmo di Kadane, osservato dalla prospettiva delle somme prefisse.
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]))
# -1Somme prefisse 2D per le query sulla griglia
Le somme prefisse si estendono anche alle griglie 2D. Definire P[i][j] come la somma di tutti gli elementi nel rettangolo da (0,0) a (i-1,j-1). Costruirlo con la formula di inclusione-esclusione: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. A quel punto, è possibile rispondere in O(1) a qualsiasi query sulla somma del rettangolo da (r1,c1) a (r2,c2) usando quattro accessi.
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 = 14Totale progressivo per l'indice di equilibrio
L'indice di equilibrio è la posizione in cui la somma degli elementi a sinistra è uguale alla somma di quelli a destra. Precalcolare la somma totale, quindi scorrere l'array da sinistra mantenendo una somma progressiva degli elementi a sinistra. La somma a destra è total - left_sum - nums[i]. Verificare l'uguaglianza in O(1) per ogni indice, ottenendo O(n) complessivo. Questo mostra come un totale progressivo possa sostituire due array separati di somme prefisse.
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])) # -1Prodotto dell'array escluso l'elemento corrente
Dato un array, restituire un array in cui ogni elemento è il prodotto di tutti gli altri. La divisione non è consentita. Usare un prodotto prefisso e un prodotto suffisso: result[i] = (prodotto di tutti gli elementi precedenti a i) × (prodotto di tutti gli elementi successivi a i). Costruire i prodotti prefissi con una scansione da sinistra a destra, quindi moltiplicare per i prodotti suffissi con una scansione da destra a sinistra usando una variabile progressiva, senza bisogno di un array aggiuntivo per il suffisso.
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 spaceSomme prefisse con modulo
Alcuni problemi chiedono il numero di sottoarray la cui somma è divisibile per k. Usando le somme prefisse modulo k: se prefix[j] % k == prefix[i] % k, allora sum(i+1..j) è divisibile per k. Una hash map che conta ogni valore del resto durante la scansione consente di ottenere tempo O(n). L'inizializzazione fondamentale è freq[0] = 1 per gestire i sottoarray che iniziano all'indice 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)Array delle differenze per gli aggiornamenti degli intervalli
Un array delle differenze è l'inverso di una somma prefissa. Dato un array, precalcolare diff[i] = nums[i] - nums[i-1]. Aggiungere x a un intervallo [l, r] richiede soltanto due operazioni O(1) sull'array delle differenze: diff[l] += x e diff[r+1] -= x. Dopo tutti gli aggiornamenti, ricostruire l'array risultato con un'unica scansione tramite somme prefisse. In questo modo, k aggiornamenti di intervalli passano da O(n×k) a 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]Le somme prefisse nei problemi dei colloqui
Le somme prefisse compaiono in molte categorie di problemi:
- Query sugli intervalli — somma del sottoarray, somma del rettangolo
- Conteggio dei sottoarray — somma uguale a k, divisibile per k
- Problemi sui prodotti — prodotto escluso l'elemento corrente
- Equilibrio — trovare l'indice pivot
- Aggiornamenti degli intervalli — array delle differenze
# 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)) # 3Somma progressiva e massimo progressivo
Oltre alle somme prefisse, molti problemi usano un massimo progressivo o un minimo progressivo mantenuto in una singola variabile. Best-time-to-buy-stock usa il prezzo minimo progressivo; trapping rain water da sinistra usa l'altezza massima progressiva a sinistra. Questi pattern richiedono una sola scansione e spazio aggiuntivo O(1), rappresentando lo standard di riferimento per l'efficienza sia temporale sia spaziale.
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])) # 5Verifica rapida
Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha appreso che: le somme prefisse trasformano le query sugli intervalli da O(n) in accessi O(1), precalcolando le somme cumulative con un'unica scansione O(n), la combinazione di somme prefisse e hash map consente soluzioni O(n) per contare i sottoarray con una determinata somma o proprietà di divisibilità e gli array delle differenze sono l'inverso: consentono aggiornamenti di intervalli in O(1), con un'unica scansione finale per ricostruire le somme prefisse. Successivamente verrà esaminata la tecnica dei due puntatori, iniziando dai puntatori alle estremità opposte.
Domande Frequenti
La lezione «Somme prefisse e totali progressivi» è gratuita?
Sì — il testo completo di «Somme prefisse e totali progressivi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Somme prefisse e totali progressivi»?
Costruisca array di somme prefisse per rispondere in O(1) a query sulle somme di intervalli e applichi la tecnica a problemi su subarray, come il subarray a somma massima Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Somme prefisse e totali progressivi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Basi degli array e operazioni in-place
- Somme prefisse e totali progressivi
- Due puntatori: estremità opposte
- Due puntatori: lento e veloce