Ö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
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.
ilk öğenin toplamı olsun. Sonra 'nin toplamı olur.
prefix[i]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.
Junior'dan Senior'a detaylı cevaplarla bir BT mülakat soruları kütüphanesi.
Bağış Yap