Prefix (Պրեֆիքս) գումարներ
Պրեֆիքս գումարները (Prefix sum) շատ օգտակար են, երբ աշխատում ենք զանգվածներում գտնվող միջակայքերի հետ: Շատ դեպքերում կարելի է խուսափել նույն գումարները մի քանի անգամ հաշվելուց, եթե նախապես պատրաստենք զանգվածի prefix (պրեֆիքս) գումարները և օգտվենք դրանցից:
Պատկերացրեք խնդիր, որտեղ անհրաժեշտ է հաճախ (օրինակ միլիոնավոր անգամներ) պատասխանել հարցին. «Ո՞րն է
a զանգվածի էլեմենտների գումարը սկզբից մինչև ինդեքսը»։ Եթե յուրաքանչյուր հարցման համար ամեն անգամ գումարենք a[0] + a[1] + a[2] + ... + a[], ապա շաա՜տ շատ դանդաղ կլինի:a = [8, 3, -2, 4, 10, -1, 0, 5] # զանգված
q = [3, 5, 2, 7] # հարցումներԵթե ամեն հարցման համար օգտագործենք
for ցիկլ, ստիպված կլինենք նորից գումարել նույն սկզբնական արժեքները:res1 = a[0] + a[1] + a[2] + a[3]
res2 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
res3 = a[0] + a[1] + a[2]
res4 = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]Նկատեք, որ ուշադիր նայելով այդ հաշվարկներին կարելի է գլխի ընկնել, որ շատ հաշվարկներ կրկնվում են և կարլի է դրանց արդյունքները մի պահել և օգտագործել հաջորդ հաշվարկների մեջ։ Օրինակ,
res2 հաշվելուց առաջ մենք արդեն գիտենք res1-ը, իսկ res4 հաշվելուց առաջ ունենք a[0] + a[1] + a[2] + a[3] + a[4] + a[5]-ի արդյունքը res2-ի մեջ: Այս ամենը կարելի է շատ ավելի արագ անել, եթե նախօրոք հաշված լինենք prefix (պրեֆիքս) գումարների զանգվածը:Դրա համար կարող ենք ստեղծել մի նոր զանգված
p անունով, որտեղ p[i]-ն կպահի a[0] + a[1] + ... + a[i] գումարը: Այդ դեպքում հարցման պատասխանը պարզապես կլինի p[]-ն:p[0] = a[0]
p[1] = a[0] + a[1]
p[2] = a[0] + a[1] + a[2]
p[3] = a[0] + a[1] + a[2] + a[3]
p[4] = a[0] + a[1] + a[2] + a[3] + a[4]
p[5] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5]
p[6] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6]
p[7] = a[0] + a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7]Տեսնում եք, որ յուրաքանչյուր հաջորդ արժեք ստանալու համար բավարար է վերցնել նախորդը և գումարել ևս մեկ էլեմենտ
a-ից:p[0] = a[0]
p[1] = p[0] + a[1]
p[2] = p[1] + a[2]
p[3] = p[2] + a[3]
p[4] = p[3] + a[4]
p[5] = p[4] + a[5]
p[6] = p[5] + a[6]
p[7] = p[6] + a[7]Այսպիսով, կարելի է բոլոր prefix (պրեֆիքս) գումարները հաշվել գծային ժամանակում ()
for ցիկլով, և ստանալ հատուկ p զանգվածը, որը հետո կարող ենք օգտագործել ամեն հարցմանն ակնթարթորեն պատասխանելու համար: Այսպիսով յուրաքանչյուր հարցման համար պատասխանն ուղղակի կլինի p[]-ն:Կարո՞ղ եք հիմա ձեր պրեֆիքս գումարների զանգվածը կառուցել:
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ ). Մուտքի երկրորդ տողում տրված են բացատով առանձնացված n ամբողջ թվեր, որոնք ներկայացնում են a զանգվածի արժեքները ():Ելք
Ծրագիրը պետք է արտածի
a զանգվածի պրեֆիքս գումարների զանգվածը:Օրինակներ
Մուտք | Ելք |
8
8 3 -2 4 10 -1 0 5 | 8 11 9 13 23 22 22 27 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 20 MB