Suma pe interval cu sume prefix iese greșită (prefix[j] - prefix[i] fără +1)
Cu prefix[k] = suma primelor k elemente, suma de la i la j inclusiv este prefix[j + 1] - prefix[i]. Dacă scrii prefix[j] - prefix[i], pierzi elementul j; dacă scrii prefix[j] - prefix[i - 1] cu altă convenție, pici la i = 0.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Sumele prefix răspund în O(1) la „cât e suma elementelor de la i la j?”. Cea mai sigură convenție: prefix are n + 1 poziții, prefix[0] = 0, iar prefix[k] e suma primelor k elemente (pozițiile 0..k-1). Atunci suma pe [i, j] inclusiv e prefix[j + 1] - prefix[i].
Greșelile tipice:
prefix[j] - prefix[i]: rezultatul lasă pe dinafară elementulj(e suma pe[i, j));- convenția
prefix[k] = suma până la k inclusivcu formulaprefix[j] - prefix[i - 1]: lai = 0,prefix[-1]e ultimul element, iar Python nu dă eroare; prefixconstruit cunpoziții în loc den + 1.
Python nu semnalează nimic: primești doar sume greșite. Testează pe interval de un singur element (i == j) și pe interval care începe la 0.
De ce apare: cauzele frecvente
1Formula exclude capătul din dreapta
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
suma = prefix[j] - prefix[i]prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
suma = prefix[j + 1] - prefix[i]prefix[j + 1] include elementul j; prefix[i] scade exact elementele dinaintea lui i.
2Prefix inclusiv și indice -1 la început
prefix = list(itertools.accumulate(nums))
suma = prefix[j] - prefix[i - 1]prefix = list(itertools.accumulate(nums))
suma = prefix[j] - (prefix[i - 1] if i > 0 else 0)La i = 0, prefix[-1] e suma totală, deci rezultatul devine greșit fără nicio eroare. Mai simplu: treci la convenția cu prefix[0] = 0.
Repară eroarea, direct în pagină
Funcția vanzari_interval(vanzari, i, j) folosește sume prefix ca să dea totalul vânzărilor din zilele i..j inclusiv. Testul cu assert pică. Repar-o ca testele să treacă și să afișeze 13, 5 și 24.
def vanzari_interval(vanzari, i, j):
prefix = [0]
for x in vanzari:
prefix.append(prefix[-1] + x)
return prefix[j] - prefix[i]
v = [5, 3, 8, 2, 6]
for i, j, corect in [(1, 3, 13), (0, 0, 5), (0, 4, 24)]:
rez = vanzari_interval(v, i, j)
assert rez == corect, f'suma gresita pe [{i}, {j}]: {rez}'
print(rez)13 5 24
Indiciu
prefix[k] e suma primelor k zile, deci suma de la i la j inclusiv începe la prefix[j + 1].
Reparația
def vanzari_interval(vanzari, i, j):
prefix = [0]
for x in vanzari:
prefix.append(prefix[-1] + x)
return prefix[j + 1] - prefix[i]
v = [5, 3, 8, 2, 6]
for i, j, corect in [(1, 3, 13), (0, 0, 5), (0, 4, 24)]:
rez = vanzari_interval(v, i, j)
assert rez == corect, f'suma gresita pe [{i}, {j}]: {rez}'
print(rez)De ce merge
Lista prefix e [0, 5, 8, 16, 18, 24]: prefix[k] adună primele k zile. prefix[j] - prefix[i] dădea suma zilelor i..j-1, deci lipsea mereu ultima zi (pentru [0, 0] ieșea chiar 0). prefix[j + 1] - prefix[i] adună zilele 0..j și scade zilele dinaintea lui i, adică exact intervalul închis cerut, inclusiv când începe la ziua 0 sau se termină la ultima.
Cum o eviți pe viitor
Folosește mereu aceeași convenție: prefix cu n + 1 poziții, începând cu 0, și formula prefix[j + 1] - prefix[i] pentru intervale închise. Scrie convenția într-un comentariu deasupra. Testează trei cazuri: un singur element (i == j), intervalul care începe la 0 și cel care se termină la ultimul element. Cu itertools.accumulate(nums, initial=0) primești direct lista cu 0 în față.
Întrebări frecvente
De ce prefix are n + 1 elemente?
Ca să existe „suma a zero elemente” la poziția 0. Așa formula merge la fel și pentru intervalul care începe la primul element, fără if.
Merge la fel și în 2D?
Da, cu o matrice (n + 1) x (m + 1) și formula cu patru termeni. Convenția cu rând și coloană de zero în față evită aceleași cazuri limită.
Erori înrudite
IndexError: list assignment index out of range Ai scris rezultat[i] = valoare pe o poziție care nu există încă în listă. O listă Python nu crește singură la atribuire. Creează lista cu lungimea potrivită (rezultat = [0] * n) sau adaugă elementele cu append. Fereastra glisantă sare peste ultima fereastră (off-by-one la range) O listă cu n elemente are n - k + 1 ferestre de lungime k, deci bucla trebuie să fie range(len(lista) - k + 1). Cu range(len(lista) - k) ultima fereastră nu e verificată, iar rezultatul e greșit fără nicio eroare. Kadane returnează 0 pentru o listă doar cu numere negative Ai pornit maximul (sau suma curentă) de la 0, iar când toate numerele sunt negative, nicio secvență nu trece de 0. Pornește de la primul element: cel_mai_bun = curent = nums[0], apoi curent = max(x, curent + x) pentru restul. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
