Perhatikan barisan bilangan berikut:
12  23  43  12  43  22  11 7  9  10  100  …
Berapakah jumlah suku ke-tiga sampai ke-sepuluh?

Cara :

HMMM…

Apakah setiap ada pertanyaan seperti itu, kita harus ngeloop dari awal sampai akhir dari suku yang ditanyakan?

Duh, gimana kalo barisannya ada ratusan ribu bahkan jutaan suku? Kita harus ngitung lagi ratusan ribu bahkan jutaan kali. BOOM!!

Tenang ^^

Ada jurus mustajab bernama PrefixSum. Dengan jurus itu, kita bisa menghitung hasil dari pertanyaan diatas cukup satu kali hitungan aja.

Yuk, kita perhatikan source code berikut, misal kita memiliki barisan sebanyak n bilangan,

Jadi,  prefixsum[i] akan menyimpan jumlah semua bilangan ke-1 sampai ke-i. Sehingga untuk menghitung jumlah semua bilangan ke-j sampai ke-k, cukup dengan sekali hitungan berikut ini:

NOTE!!

prefixsum[i] harus diawali dengan i=1. Karena jika diawali i=0, compiler tidak dapat megenali prefixsum[-1]

Aplikasi dari Prefixsum:

  1. Digunakan untuk berbagai permasalah dalam soal competitive programming
  2. Mempermudah proses komputasi dalam kasus berskala besar

Itu tadi gambaran sederhana dari Prefixsum. Semoga bermanfaat. ^^

-CP