# Prefix Sum
Penulis: Sayed Aulia, Polikarpus Arya Pradhanika
<div style="text-align: justify">

> Pada artikel ini kita akan menggunakan sistem indeks $1$.

Anggap saja kita memiliki suatu array $a$ dengan panjang $N$, katakanlah array tersebut memiliki panjang $7$ dan berisikan bilangan bulat $\{1, 2, 3, 4, 5, 6, 7 \}$. Apabila kita ingin mengeluarkan jumlah dari indeks pada rentang indeks $l$ hingga $r$ atau secara formal $a_l + a_{l+1} + \cdots + a_{r-1} + a_r$, kita dapat mengiterasikan indeks dari $l$ hingga $r$ dan menjumlahkannya pada suatu variable $\texttt{sum}$ dengan program berikut:

int a[] = {0, 1, 2, 3, 4, 5, 6, 7};

int l, r;
cin >> l >> r;

int sum = 0;
for(int i = l; i <= r; i++){
    sum += a[i];
}
    
cout << sum;

Program ini akan memberikan kompleksitas $\mathcal{O}(N)$.

Akan tetapi apabila kita diberikan $Q$ buah pertanyaan di mana setiap pertanyaan $i$ menanyakan jumlah dari seluruh bilangan pada rentang $l_i$ hingga $r_i$, maka solusi di atas setidaknya akan membutuhkan kompleksitas $O(NQ)$. Apabila batasan soal memberikan $N, Q < 10^5$, maka dalam kasus terburuknya program di atas akan menjalankan $10^{10}$ kali operasi di mana tentunya akan melampaui batas waktu. Beruntungnya, kita dapat menyelesaikan soal di atas menggunkan teknik yang kita sebut sebagai *Prefix Sum* dalam waktu $\mathcal{O}(Q)$ saja.

*Prefix Sum* merupakan salah satu *Range Queries* yang dapat menjawab pertanyaan dari jumlah element-element array pada rentang $l$ hingga $r$ dalam waktu $\mathcal{O}(1)$ saja. Ide utama pada teknik ini ialah kita ingin menymimpan jumlah dari elemen ke-$1$ hingga $i$ untuk setiap $1 \le i \le n$ dan memasukkan hasilnya pada suatu array baru $\texttt{prefix}$ di mana $\texttt{prefix}[i]$ menyimpan jumlah dari elemen ke-$1$ hingga ke-$i$.

Perhatikan bahwa $$ \texttt{prefix}[k] = \sum_{i=0}^{k} a[i]$$

maka untuk melakukan *precomputation*, kita dapat memanfaatkan persamaan
$$\texttt{prefix}[k] = \sum_{i=0}^{k} a[i] \\
\texttt{prefix}[k] = \sum_{i=0}^{k - 1} a[i] + a[k] \\
\texttt{prefix}[k] = \texttt{prefix}[k - 1] + a[k]$$

Perlu diingat bahwa *Prefix Sum* umumnya menggunakan $1$ *based indexing* maka kita ingin menetapkan nilai $a[0] = 0.$ Apabila array awal adalah $a$ dan berisikan $\{0, 1, 3, 2, 4, 7, 2, 5 \}$ maka array $\texttt{prefix}$ akan berisikan $\{0, 1, 4, 6, 10, 17, 19, 24 \}$. Dan dapat dilihat bahwa apabila kita ingin mengambil jumlah dari rentang $l$ hinga $r$ kita cukup mengeluarkan $\texttt{prefix}[r] - \texttt{prefix}[l-1]$ sebagaimana diilustrasikan di bawah ini:

### Implementasi

// array a yang telah di-prekomputasi
int a[8] = {0, 1, 2, 3, 4, 5, 6, 7};

int prefix[8];
    
// basis
prefix[0] = 0;

// transisi
for(int i = 1; i < 8; i++){
    prefix[i] = prefix[i - 1] + a[i];                     
}
    
int l, r;
cin >> l >> r;
// untuk query cukup keluarkan prefix[r] - prefix[l - 1] saja
int sum = prefix[r] - prefix[l - 1];
    
cout << sum << '\n';

Sehingga untuk kompleksitas dari program prefix sum adalah $\mathcal{O}(N)$ untuk *precompute* dan $\mathcal{O}(1)$ untuk setiap *query*

#### Catatan Kaki
Walau demikian, *Prefix Sum* juga memiliki beberapa kelemahan yakni ia tidak dapat melakukan query untuk operasi yang tidak memiliki invers seperti mencari nilai maksimum maupun minimum pada suatu rentang tertentu, hal ini dapat dilakukan menggunakan *range queries* yang lebih mutakhir seperti *Segment Tree*.

Selain itu, *Prefix Sum* juga tidak dapat melakukan *update* yakni mengubah nilai pada suatu indeks dengan nilai lain dengan cepat, operasi tersebut dapat dilakukan oleh *Segment Tree* dengan waktu $\mathcal{O}(\log N)$ sedangkan prefix sum harus membangun array baru untuk melakukan operasi tersebut dalam waktu $\mathcal{O}(N)$.

</div>