Jumlah prefiks

Kueri rentang adalah pertanyaan berulang tentang jumlah elemen pada sebuah potongan array, misalnya total menit belajar dari hari ketiga sampai kelima. Menjumlahkan ulang untuk setiap kueri berbiaya $O(n)$, dan ratusan kueri berarti pekerjaan yang sama diulang ratusan kali. Teknik jumlah prefiks (prefix sum) membangun array pembantu satu kali dalam $O(n)$, lalu menjawab setiap kueri dalam $O(1)$ dengan selisih dua sel. Topik ini membangun arraynya dari kasus nyata, membuktikan rumus kuerinya, dan menimbang harganya.

Kueri rentang yang dijawab berulang-ulang#

Ambil contoh catatan menit belajar harian selama seminggu, disimpan sebagai array [45, 60, 30, 0, 75, 120, 90]. Pertanyaan berupa jumlah rentang bisa datang berkali-kali dengan rentang yang berbeda, misalnya total tiga hari pertama untuk laporan, atau total hari kedua sampai keempat untuk evaluasi. Setiap pertanyaan meminta penjumlahan atas satu potongan array, dan tidak ada yang tahu rentang mana yang akan ditanyakan berikutnya.

Menjumlahkan langsung untuk setiap kueri memindahkan hingga $O(n)$ elemen per pertanyaan. Dengan $q$ kueri, total kerjanya menjadi $O(q \cdot n)$, dan $q$ yang besar menjadikan pola ini mahal meskipun tiap kueri terlihat sederhana. Padahal arraynya tidak berubah antar kueri, sehingga penjumlahan yang sama dihitung ulang tanpa alasan. Situasi data yang statis dan pertanyaan yang banyak justru menjadi peluang, karena hasil perhitungan yang berulang dapat disimpan sekali untuk dipakai terus.

Bangun array prefix dalam satu lintasan#

Array prefix menyimpan jumlah akumulasi, yaitu elemen ke-$i$ berisi penjumlahan seluruh elemen asli dari awal sampai indeks $i - 1$. Sel pertama sengaja diisi 0 sebagai titik nol, sehingga rentang yang dimulai dari indeks 0 tetap memakai rumus yang sama tanpa perlakuan khusus. Setiap sel berikutnya dihitung dari sel sebelumnya lewat $\text{prefix}[i+1] = \text{prefix}[i] + a[i]$, sehingga pembangunannya selesai dalam satu lintasan berbiaya $O(n)$. Tidak ada pengulangan bersarang sama sekali dalam pembangunannya.

Diagram berikut memasangkan array menit belajar dengan array prefix-nya. Dua sel yang disorot pada baris kedua adalah sel yang dipakai untuk menjawab satu kueri rentang, yaitu jumlah hari ke-2 sampai ke-4.

Bandingkan panjang kedua barisnya, array prefix selalu satu sel lebih panjang karena sel nol di depan. Nilai pada sel indeks 3 adalah 135, yang berarti total 135 menit sudah terkumpul sampai hari kedua. Dengan kata lain, setiap sel menyimpan jawaban untuk satu pertanyaan kumulatif, dan pertanyaan rentang tinggal memanfaatkan dua jawaban kumulatif itu.

Kueri rentang dalam O(1)#

Jumlah elemen dari indeks $l$ sampai $r$ adalah selisih dua sel prefix, yaitu $\text{prefix}[r+1] - \text{prefix}[l]$. Intuisinya lurus, prefix ke $r+1$ sudah mencakup semua elemen sampai indeks $r$, sedangkan prefix ke $l$ mencakup semua elemen sebelum indeks $l$. Mengurangi keduanya membuang bagian yang tidak ditanyakan dan menyisakan persis potongan $l$ sampai $r$. Satu pengurangan, dua pembacaan sel, tanpa penjumlahan ulang.

Demo berikut membangun array prefix sekali, lalu menjawab tiga kueri dengan fungsi yang sama.

"""Jumlah prefiks: dibangun sekali dalam O(n), kueri rentang dijawab dalam O(1)."""

menit_belajar = [45, 60, 30, 0, 75, 120, 90]   # menit belajar harian selama seminggu

prefix = [0] * (len(menit_belajar) + 1)        # sel pertama sengaja bernilai 0
for i, nilai in enumerate(menit_belajar):
    prefix[i + 1] = prefix[i] + nilai

print("array prefix    :", prefix)


def jumlah_rentang(l, r):
    """Total menit dari hari ke-l sampai hari ke-r (indeks mulai dari 0)."""
    return prefix[r + 1] - prefix[l]


print("total hari 0-2  :", jumlah_rentang(0, 2))
print("total hari 2-4  :", jumlah_rentang(2, 4))
print("total hari 0-6  :", jumlah_rentang(0, 6))

array prefix    : [0, 45, 105, 135, 135, 210, 330, 420]
total hari 0-2  : 135
total hari 2-4  : 105
total hari 0-6  : 420

Tiga kueri pada demo dijawab tanpa satu pun penjumlahan ulang atas array aslinya, termasuk kueri pertama yang rentangnya dimulai dari indeks 0. Setelah pembangunan, setiap kueri berbiaya tetap, sehingga pola $O(q \cdot n)$ runtuh menjadi $O(n + q)$. Inilah wujud dari pola umum pra-penghitungan (precomputation), yaitu membayar satu kali di awal untuk mempercepat seluruh pertanyaan yang datang setelahnya.

Harga yang dibayar dan varian lainnya#

Array prefix menambah $O(n)$ memori pembantu, dan keuntungannya hanya berlaku selama array aslinya tidak berubah. Satu pembaruan nilai pada array asli memaksa sel-sel prefix sejak posisi itu sampai akhir dihitung ulang, yang dalam kasus terburuk berbiaya $O(n)$. Teknik ini paling pas untuk data yang sudah selesai terbentuk dan hanya dibaca, seperti catatan harian yang telah lampau. Ketika pembaruan terjadi sepanjang waktu, struktur yang lebih serasi dibutuhkan, misalnya Fenwick tree atau segment tree, dan keduanya tumbuh dari intuisi yang sama.

Ide jumlah akumulasi juga merambat ke varian lain yang layak dikenal namanya. Jumlah prefiks xor mengganti penjumlahan dengan operasi xor, sehingga kueri xor sebuah rentang dijawab dengan menggabungkan dua sel prefix yang sama. Adapun versi dua dimensi menyimpan jumlah persegi pada tabel dan menjawab kueri wilayah dalam $O(1)$. Semuanya memakai resep yang identik, yaitu membayar satu lintasan awal supaya setiap kueri tinggal membaca beberapa sel. Mengenali pola ini mempercepat pembacaan banyak soal nantinya.

Kesalahan umum#

1. Memakai prefix[r] alih-alih prefix[r + 1]. Hasilnya kekurangan satu elemen terakhir, yaitu elemen di indeks $r$ yang justru termasuk rentang. Kekeliruan ini tidak memunculkan error apa pun, keluarannya hanya meleset diam-diam.
2. Membangun prefix tanpa sel nol di depan. Kueri dengan $l = 0$ kemudian butuh percabangan khusus karena tidak ada titik nol untuk dikurangkan. Sel nol memang menghabiskan satu slot, tetapi menghilangkan seluruh kasus khusus itu.
3. Membangun ulang prefix untuk setiap kueri. Biaya kembali menjadi $O(q \cdot n)$ dan seluruh keunggulan teknik ini lenyap. Prefix hanya perlu dibangun ulang setelah data aslinya benar-benar berubah.

Ringkasan#

• Array prefix menyimpan jumlah akumulasi dengan sel nol di depan, dibangun sekali dalam $O(n)$.
• Jumlah rentang $l$ sampai $r$ dijawab dengan $\text{prefix}[r+1] - \text{prefix}[l]$ dalam $O(1)$ per kueri.
• Harganya $O(n)$ memori tambahan dan pembaruan data asli yang mahal, sehingga paling pas untuk data statis dengan banyak kueri.
• Varian xor dan dua dimensi memakai resep yang sama, yaitu pra-penghitungan sekali untuk banyak kueri.

Referensi#

• Prefix sum — Wikipedia — definisi jumlah prefiks, rumus kueri rentang, dan varian dua dimensinya.
• Data Structures — Python Software Foundation — dokumentasi list Python yang dipakai untuk membangun array prefix pada demo.