Prefix sums
Në shqip: Shumat paraprake
ShpjegimiSQ
Me shumat paraprake, llogarit një herë shumën nga fillimi deri te çdo pozicion. Pastaj shumën e çdo pjese të listës e merr në një hap: p[j] - p[i]. Shumë e dobishme në gara programimi.
EnglishEN
With prefix sums, you calculate once the sum from the start up to each position. Then the sum of any slice of the list takes one step: p[j] - p[i]. Very handy in programming contests.
Si ta mendosh
Si kilometrazhi i veturës: për të ditur sa ke ecur mes dy qyteteve, zbret dy numra, s'i numëron kilometrat sërish.
Lexoje në anglisht
Like a car's odometer: to know how far you drove between two towns, you subtract two numbers instead of recounting.
Shembull kodipython
from itertools import accumulate
v = [3, 1, 4, 1, 5]
p = [0, *accumulate(v)] # [0, 3, 4, 8, 9, 14]
print(p[4] - p[1]) # shuma e v[1:4] = 6