Önek Toplam Dizisi Oluşturma

Tek bir dizi üzerinde yüzlerce aralık toplamı sorusunu yanıtladığınızı düşünün. Her aralığı baştan toplamak yavaştır. Bir önek toplamı bunu çözer. 🚀

Bir önek toplamı dizisi, her indekste o noktaya kadar olan tüm öğelerin toplamını saklar. Önceden yapılan tek bir geçiş, yavaş toplamları anında alınan yanıtlara dönüştürür.

[3, 1, 4] için biriken toplamlar önce 3, sonra 4, ardından 8 olur. Büyüyen bu toplamlar listesi tam olarak önek toplamınızdır.

Her öğe, önceki toplam ile geçerli öğenin toplamıdır. Bu tek satırlık bağıntı, tekniğin tamamının temelidir.

Dizide bir kez ilerlerken biriken toplamı taşıyın. Her adımda yeni toplamı eklediğiniz için diziyi oluşturmak tek bir doğrusal geçiştir.

Öne bir sıfır koyarak başlamak, prefix[i] değerinin ilk i öğenin toplamını tutması anlamına gelir. Bu, daha sonra aralık hesaplarını düzenli hâle getirir.

Önde sıfır varken prefix[k], a[0] + ... + a[k-1] değerine eşittir. Bu kuralı doğru uygulamak, can sıkıcı birer-bir eksik hatalarını önler.

Önek toplamı dizisini oluştururken her öğeye tam olarak bir kez dokunulur; bu nedenle maliyet O(n) zamandır. Bu bedeli bir kez öder, ardından diziyi tekrar tekrar kullanırsınız.

Asıl kazanç şu ödünleşimdir: başta bir doğrusal geçiş harcayarak sonraki her toplam sorgusunu döngü yerine hızlı bir aramaya dönüştürürsünüz.

Standart kitaplık toplamları sizin için oluşturabilir. itertools.accumulate, birikerek oluşan toplamları tek ve temiz bir çağrıyla üretir.

Önek toplamı dizisi, girdinizle aynı uzunluğa ek olarak bir öğe daha içerir. Çok büyük girdilerde bellek ayak izinizi iki katına çıkardığını unutmayın.

Bir önek toplamı dizisi oluşturuyorsunuz. 0 indeksi genellikle ne tutar?

Baştaki sıfır sayesinde temiz indekslemeyle tek bir O(n) geçişinde önek toplamı dizisi oluşturmayı öğrendiniz. Bir kez önceden hesaplayın, sonra yeniden kullanın. ✅