Biraz dizi olsun. Değişiklik olmadığında, bu dizinin bir alt bölümündeki bazı işlevlerin değerini hızlı bir şekilde (bir satırdan daha hızlı) bulabiliriz. Bunun için ek bellek kullanmamız ve bir ön hesaplama yapmamız gerekiyor.
Örneğin, dizinin bir bölümündeki toplamı hızlı bir şekilde bulmamız gerekiyor.
Önek toplamlarından oluşan bir dizi elde edelim, burada i indeksi, indeksleri i'den küçük veya i'ye eşit olan dizinin tüm öğelerinin toplamı olacaktır.
bir[] – verilen dizi, p[] – önek toplamı dizisi
Dizi sayısı p:
Açıkçası p[0] = a[0]. p[i]'yi p[i – aracılığıyla kolayca yeniden hesaplayabileceğimize dikkat edin. 1], çünkü i öneki üzerindeki miktar, i öneki üzerindeki miktardır – 1 + a[i].
Böylece, önek toplamlarını hesaplama kodu şöyle görünür:
int a[n], p[n];
p[0] = a[0< /span>];
için (int ve = 1; i < n; i++)
p[i] = p[i - 1] + a[i];
Ayrıca, segmentteki toplamın – önekteki iki toplam arasındaki fark.
Yeşil = kırmızı – mavi
Dolayısıyla, [l,r] aralığındaki toplamı bulmak gerekiyorsa, cevap p[r] – p[l-1].
Ancak, eğer ben – 1 öğe olmayabilir. if’s olmadan yapmak için, 1 indeksleme girebilirsiniz ve a[0] ve p[0] nötr değerlere sahip olacaktır (toplam için 0).
Bu tekniğin dahil etme-dışlama formülünün özel bir durumu olduğunu unutmayın, dolayısıyla bu şekilde yalnızca toplamları değil, çarpma ve xor gibi diğer işlevleri de depolamak mümkündür.