Prefiksi
★☆☆ laganoIspiš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
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.
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.
Trik: zbrojeve izračunamo jednom, unaprijed, pa svako pitanje odgovorimo u jednom koraku.
Prefiksni zbroj (engl. prefix sum) p[i] je zbroj prvih i elemenata liste. „Prefiks“ znači početni dio. Uvijek je p[0] = 0.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| a (dan i) | 3 | 1 | 4 | 1 | 5 | 9 | |
| p[i] | 0 | 3 | 4 | 8 | 9 | 14 | 23 |
Svaki prefiksni zbroj dobijemo iz prethodnog, dodavanjem jednog elementa: p[i] = p[i − 1] + a[i − 1]. Cijela lista p gradi se jednim prolazom.
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.
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])
Pripremu radimo jednom, O(N). Svako pitanje je zatim O(1). Ukupno O(N + Q) umjesto O(N · Q).
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)
Koja su to tri dana u primjeru?
Zadnja tri: 1 + 5 + 9 = 15.
Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.
P[i] je zbroj prvih i elemenata. Kako dobiti zbroj od a-tog do b-tog?
Oduzmemo sve što je prije a.
Koliko koraka treba za Q upita nakon što izračunamo prefiksne zbrojeve?
Svaki upit je jedno oduzimanje.
Koliko je P[0] u prefiksnom zbroju?
Zbroj nula elemenata je 0; to olakšava formulu.
Ispiši sve prefiksne zbrojeve p[1], p[2], …, p[N].
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).
Zbrajanje petljom za svako pitanje neće stići. Pripremi prefiksne zbrojeve, a svako pitanje je onda jedno oduzimanje.
Za N dana znamo zaradu. Koliko je najviše zarađeno u K uzastopnih dana?
Kreni od zbroja prvih K dana, a ne od 0, jer zbrojevi mogu biti negativni.
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.
Zbroj lijevo od i-tog je p[i − 1]. Zbroj desno je ukupni zbroj p[N] umanjen za p[i].
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