Sumy prefiksowe

Obliczanie sum elementów w przedziałach

Pomysł polega na użyciu sum prefiksowych p0, p1, p2 ... pn. Są to kolejne sumy 0, 1, 2, ... n początkowych elementów tablicy.

Suma prefiksowa jest to suma danej ilości początkowych elementów tablicy.

Żeby ją zastosować, potrzebujemy dodatkowej tablicy. Nazwijmy ją sum_prefiksowa.
1. int sum_pref[n+1];
Zauważmy, że nowa tablica jest o jeden element większa od pierwszej. Kolejnym krokiem jest takie wypełnienie tej tablicy:

1. sum_prefiksowa[0] = 0;
2. for(int i=0; i < n; ++i)
3. sum_pref[i+1] = sum_pref[i] + t[i];