Prefiks cəmləri massivin ilk i elementinin cəmini əvvəlcədən hesablayıb saxlamaqdır. Bu bir dəfəlik O(n) hazırlıq istənilən kəsimin cəmini O(1)-də verir. Eyni ideyanın tərsi fərq massivi kəsimə kütləvi yeniləməni O(1)-də edir.
![a[2..5] cəmi P[6] - P[2] = 19](img/lessons/algorithms/prefix-sums-range-query.svg)
Prefiks massivi və kəsim sorğusu
Tərifə görə prefix[0] = 0, prefix[i] = a[0] + ... + a[i-1]. a[l..r] (hər iki ucu daxil) cəmi prefix[r + 1] - prefix[l] olur, çünki fərq a[0..r]-dən a[0..l-1]-i çıxır. Əvvəldəki 0 sol sərhəd (l = 0) üçün istisnanı aradan qaldırır. Hazırlıq üçün itertools.accumulate kifayətdir.
from itertools import accumulate
a = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0] + list(accumulate(a)) # prefix[i] = sum(a[:i])
def range_sum(l, r): # inclusive bounds
return prefix[r + 1] - prefix[l]
print(prefix)
print(range_sum(2, 5), range_sum(0, 7), range_sum(3, 3))