...
Eroare Algoritmi și structuri de date · Tablouri, două pointere și ferestre

Suma pe interval cu sume prefix iese greșită (prefix[j] - prefix[i] fără +1)

Pe scurt

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ă elementul j (e suma pe [i, j));
  • convenția prefix[k] = suma până la k inclusiv cu formula prefix[j] - prefix[i - 1]: la i = 0, prefix[-1] e ultimul element, iar Python nu dă eroare;
  • prefix construit cu n poziții în loc de n + 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

Greșit
PYTHON
prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
suma = prefix[j] - prefix[i]
Corect
PYTHON
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

Greșit
PYTHON
prefix = list(itertools.accumulate(nums))
suma = prefix[j] - prefix[i - 1]
Corect
PYTHON
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ă tu

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.

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
13
5
24
Indiciu

prefix[k] e suma primelor k zile, deci suma de la i la j inclusiv începe la prefix[j + 1].

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.