Python stazaCjelina 4 · Prvi algoritmiLekcija 26

Prefiksni zbroj (prefix sum)

Koliko je trgovina zaradila od 10. do 40. dana? Ako takvih pitanja ima sto tisuća, svako zbrajanje ispočetka je presporo. Prefiksni zbroj odgovara u jednom koraku.

Pythonoko 45 minuta4 zadatka za evaluator

1Problem: mnogo pitanja o zbrojevima

Trgovina je zapisala zaradu za svaki dan u godini. Vlasnik postavlja pitanja: koliko je zarađeno od 10. do 40. dana? A od 100. do 250.? Takvih pitanja može biti 100 000.

Zbrajanje dijela liste petljom za svako pitanje traje do N koraka. Za N = 100 000 dana i Q = 100 000 pitanja to je do 10 milijardi koraka: presporo, kao što smo vidjeli u lekciji 25.

Ključna ideja

Trik: zbrojeve izračunamo jednom, unaprijed, pa svako pitanje odgovorimo u jednom koraku.

2Prefiksni zbroj

Prefiksni zbroj (engl. prefix sum) p[i] je zbroj prvih i elemenata liste. „Prefiks“ znači početni dio. Uvijek je p[0] = 0.

i0123456
a (dan i)314159
p[i]034891423

Svaki prefiksni zbroj dobijemo iz prethodnog, dodavanjem jednog elementa: p[i] = p[i − 1] + a[i − 1]. Cijela lista p gradi se jednim prolazom.

x–
p–
Klikni „Sljedeći korak“ i prati što se događa.
Pazi

Lista p ima jedan element više od liste a, jer počinje nulom. p[i] je zbroj prvih i elemenata, a ne zbroj do indeksa i.

3Zbroj dijela u jednom koraku

Koliki je zbroj od dana l do dana r (dani su numerirani od 1)? To je zbroj prvih r dana, umanjen za zbroj prvih l − 1 dana:

zbroj = p[r] - p[l - 1]

Za dane od 3 do 5 u primjeru: p[5] − p[2] = 14 − 4 = 10. Provjera: 4 + 1 + 5 = 10.

n = int(input())
a = list(map(int, input().split()))
p = [0]
for x in a:
    p.append(p[-1] + x)
q = int(input())
for k in range(q):
    l, r = map(int, input().split())
    print(p[r] - p[l - 1])
Ulaz
6 3 1 4 1 5 9 3 3 5 1 6 2 2
Ispis
10 23 1
Ključna ideja

Pripremu radimo jednom, O(N). Svako pitanje je zatim O(1). Ukupno O(N + Q) umjesto O(N · Q).

4Najbolji niz od K uzastopnih

Prefiksni zbroj pomaže i kad tražimo najbolji dio liste. Kojih K uzastopnih dana je donijelo najveću zaradu? Isprobamo svaki početak, a zbroj svakog dijela dobijemo iz p u jednom koraku.

n, k = map(int, input().split())
a = list(map(int, input().split()))
p = [0]
for x in a:
    p.append(p[-1] + x)
naj = p[k] - p[0]
for kraj in range(k, n + 1):
    if p[kraj] - p[kraj - k] > naj:
        naj = p[kraj] - p[kraj - k]
print(naj)
Ulaz
6 3 3 1 4 1 5 9
Ispis
15
Stani i razmisli

Koja su to tri dana u primjeru?

Pogledaj odgovor

Zadnja tri: 1 + 5 + 9 = 15.

5Provjeri se

Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.

Pitanje

P[i] je zbroj prvih i elemenata. Kako dobiti zbroj od a-tog do b-tog?

Pitanje

Koliko koraka treba za Q upita nakon što izračunamo prefiksne zbrojeve?

Pitanje

Koliko je P[0] u prefiksnom zbroju?

6Zadaci

Prefiksi

★☆☆ lagano

Ispiši sve prefiksne zbrojeve p[1], p[2], …, p[N].

Ulaz
U prvom retku N. U drugom retku N cijelih brojeva.
Izlaz
N brojeva u jednom retku, odvojenih razmakom.
Ograničenja
1 ≤ N ≤ 100 000, brojevi su od −1000 do 1000
Ulaz
4 2 -1 5 3
Izlaz
2 1 6 9
Riješi u evaluatoru

Zbroj dijela

★★☆ srednje

Zadana je lista od N brojeva i Q pitanja. Za svako pitanje l, r ispiši zbroj elemenata od l-tog do r-tog (elementi su numerirani od 1).

Ulaz
U prvom retku N, u drugom N brojeva. U trećem retku Q, zatim Q redaka s brojevima l i r.
Izlaz
Q redaka s odgovorima.
Ograničenja
1 ≤ N, Q ≤ 100 000, 1 ≤ l ≤ r ≤ N, brojevi su od −1000 do 1000
Ulaz
6 3 1 4 1 5 9 3 3 5 1 6 2 2
Izlaz
10 23 1
Treba ti pomoć?

Zbrajanje petljom za svako pitanje neće stići. Pripremi prefiksne zbrojeve, a svako pitanje je onda jedno oduzimanje.

Riješi u evaluatoru

Najbolji tjedan

★★☆ srednje

Za N dana znamo zaradu. Koliko je najviše zarađeno u K uzastopnih dana?

Ulaz
U prvom retku N i K. U drugom retku N cijelih brojeva.
Izlaz
Najveći zbroj K uzastopnih brojeva.
Ograničenja
1 ≤ K ≤ N ≤ 100 000, brojevi su od −1000 do 1000
Ulaz
6 3 3 1 4 1 5 9
Izlaz
15
Ulaz
5 2 -1 -5 -2 -8 -1
Izlaz
-6
Treba ti pomoć?

Kreni od zbroja prvih K dana, a ne od 0, jer zbrojevi mogu biti negativni.

Riješi u evaluatoru

Ravnoteža

★★★ teže

Postoji li mjesto i takvo da je zbroj svih elemenata lijevo od i-tog jednak zbroju svih elemenata desno od njega? Sam i-ti element ne pripada nijednoj strani. Ispiši najmanji takav i (elementi su numerirani od 1) ili −1 ako ne postoji.

Ulaz
U prvom retku N. U drugom retku N cijelih brojeva.
Izlaz
Najmanji takav i ili −1.
Ograničenja
1 ≤ N ≤ 100 000, brojevi su od −1000 do 1000
Ulaz
5 2 3 9 1 4
Izlaz
3
Ulaz
3 1 2 3
Izlaz
-1
Treba ti pomoć?

Zbroj lijevo od i-tog je p[i − 1]. Zbroj desno je ukupni zbroj p[N] umanjen za p[i].

Riješi u evaluatoru
Vježbaj dalje: zadaci s natjecanja

Ovi zadaci s Infokupa traže upravo ovo gradivo. Kreni od prvoga.

  1. Tablica Infokup 2018 · državno · 7. r. OŠ
  2. Legići Infokup 2021 · županijsko · 8. r. OŠ

7Što smo naučili

  • p[i] je zbroj prvih i elemenata; p[0] = 0.
  • p se gradi jednim prolazom: p.append(p[-1] + x).
  • Zbroj od l-tog do r-tog elementa je p[r] − p[l − 1].
  • Priprema O(N), svako pitanje O(1).
Najčešće greške

Pomak indeksa za jedan (p ima N + 1 elemenata) · p[l] umjesto p[l − 1] · najbolji zbroj koji kreće od 0 kod negativnih brojeva