Skip to content

Prefix Sum

Prefix Sum dizisi bir dizinin prefixlerinin toplamlarıyla oluşturulan bir veri yapısıdır. Prefix sum dizisinin \(i\) indeksli elemanı girdi dizisindeki \(1\) indeksli elemandan \(i\) indeksli elemana kadar olan elemanların toplamına eşit olacak şekilde kurulur. Başka bir deyişle:

\[sum_i = \sum_{j=1}^{i} {a_j}\]

Örnek bir \(A\) dizisi için prefix sum dizisi şu şekilde kurulmalıdır:

A Dizisi \(4\) \(6\) \(3\) \(12\) \(1\)
Prefix Sum Dizisi \(4\) \(10\) \(13\) \(25\) \(26\)
\(4\) \(4+6\) \(4+6+3\) \(4+6+3+12\) \(4+6+3+12+1\)

Prefix sum dizisini kullanarak herhangi bir \([l,r]\) aralığındaki elemanların toplamını şu şekilde kolaylıkla elde edebiliriz:

\[sum_r = \sum_{j=1}^{r} {a_j}\]

\[sum_{l - 1} = \sum_{j=1}^{l - 1} {a_j}\]

\[sum_r - sum_{l-1} = \sum_{j=l}^{r} {a_j}\]

Örnek Kod Parçaları

Prefix Sum dizisini kurarken \(sum_i = sum_{i - 1} + a_i\) eşitliği kolayca görülebilir ve bu eşitliği kullanarak \(sum[]\) dizisini girdi dizisindeki elemanları sırayla gezerek kurabiliriz:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
const int n;
int sum[n + 1], a[n + 1];
// a dizisi girdi dizimiz, sum dizisi de prefix sum dizimiz olsun.

void build() {
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];
    return;
}

int query(int l, int r) {
    return sum[r] - sum[l - 1];
}

Zaman Karmaşıklığı

Prefix sum dizisini kurma işlemimizin zaman ve hafıza karmaşıklığı \(\mathcal{O}(N)\). Her sorguya da \(\mathcal{O}(1)\) karmaşıklıkta cevap verebiliyoruz.

Prefix sum veri yapısı ile ilgili örnek bir probleme buradan ulaşabilirsiniz.