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 զանգվածի պրեֆիքս գումարների զանգվածը:

Օրինակներ