Ön ek toplamı dizisi birikimli toplamları depolar, böylece herhangi bir aralık toplamı O(n) ön işlemeden sonra O(1) içinde yanıtlanabilir — sorgu başına O(n) yerine.
Fikir
prefix[i] ilk öğenin toplamı olsun. Sonra 'nin toplamı olur.
Ön ek toplamı dizisi birikimli toplamları depolar, böylece herhangi bir aralık toplamı O(n) ön işlemeden sonra O(1) içinde yanıtlanabilir — sorgu başına O(n) yerine.
prefix[i] ilk öğenin toplamı olsun. Sonra 'nin toplamı olur.
iarr[l..r]prefix[r+1] - prefix[l]def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, x in enumerate(arr):
prefix[i + 1] = prefix[i] + x # running total
return prefix
def range_sum(prefix, l, r): # inclusive l..r
return prefix[r + 1] - prefix[l] # O(1)
p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3) # 4+1+3 -> 8
arr = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
Statik veriler üzerinde birden fazla aralık-toplam sorgusu için ideal. Varyantlar: alt matris toplamları için 2D ön ek toplamları, ön ek XOR ve aralık güncellemeleri için farklılık dizileri. Dizi sık sık değişiyorsa, bunun yerine bir Fenwick/segment ağacı kullanın. Dizin ofseti konusunda dikkat edin (boyut n+1).
Ön ek toplamları tekrarlanan O(n) aralık sorgularını O(1) aramalara dönüştürür — sorgular sık olduğunda büyük bir kazanç.
Bir kez ön hesapla ve hızlı yanıtla deseni birçok veri işleme görevine genelleşir.
Bu, rekabetçi programlamanın temel taşı ve analitiklerde yaygın bir yapı taşıdır.