Membangun Array Jumlah Awalan
Menghitung total berjalan terlebih dahulu satu kali
Membangun Array Jumlah Awalan adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Masalah Jumlah yang Berulang
Bayangkan Anda harus menjawab ratusan pertanyaan jumlah rentang pada satu larik. Menjumlahkan setiap rentang dari awal akan lambat. Jumlah prefiks mengatasinya. 🚀
Apa Itu Jumlah Prefiks
Larik jumlah prefiks menyimpan, pada setiap indeks, total semua elemen hingga posisi tersebut. Satu kali perhitungan awal mengubah penjumlahan lambat menjadi jawaban seketika.
Contoh Singkat
Untuk [3, 1, 4], jumlah berjalannya adalah 3, lalu 4, kemudian 8. Daftar jumlah yang terus bertambah itu persis merupakan jumlah prefiks Anda.
Rekurensi Inti
Setiap entri merupakan jumlah sebelumnya ditambah elemen saat ini. Rekurensi satu baris ini adalah inti dari seluruh teknik tersebut.
prefix[i] = prefix[i - 1] + a[i]Bangun dengan Kode
Telusuri larik sekali sambil menyimpan jumlah berjalan. Pada setiap langkah, tambahkan jumlah baru, sehingga pembangunan larik menjadi satu lintasan linear.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Mengapa Nol di Awal Membantu
Memulai larik jumlah prefiks dengan nol di awal berarti prefix[i] menyimpan jumlah i elemen pertama. Ini membuat perhitungan rentang menjadi rapi nantinya.
Konvensi Pengindeksan
Dengan angka nol di depan, prefix[k] sama dengan a[0] + ... + a[k-1]. Memahami konvensi ini dengan benar mencegah kesalahan off-by-one yang menyulitkan.
Biaya Pembangunan
Membangun larik jumlah prefiks menyentuh setiap elemen tepat satu kali, sehingga memerlukan waktu O(n). Anda membayar biaya ini sekali, lalu menggunakannya kembali tanpa batas.
Hitung Awal Sekali, Ajukan Pertanyaan Berkali-kali
Keuntungan besarnya adalah pertukaran: gunakan satu lintasan linear di awal agar setiap pertanyaan jumlah berikutnya menjadi pencarian cepat, bukan perulangan.
Pintasan Python
Pustaka standar dapat membangun jumlah untuk Anda. itertools.accumulate menghasilkan jumlah berjalan dalam satu pemanggilan yang rapi.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Perhatikan Memori
Larik jumlah prefiks memiliki panjang yang sama dengan masukan Anda ditambah satu. Untuk masukan yang sangat besar, ingat bahwa larik ini menggandakan penggunaan memori Anda.
Pemeriksaan Singkat
Anda membangun larik jumlah prefiks. Apa yang biasanya disimpan oleh indeks 0?
Rangkuman
Anda telah mempelajari cara membangun larik jumlah prefiks dalam satu lintasan O(n), dengan nol di awal untuk pengindeksan yang rapi. Hitung awal sekali, lalu gunakan kembali. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Membangun Array Jumlah Awalan” gratis?
Ya — teks lengkap “Membangun Array Jumlah Awalan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Membangun Array Jumlah Awalan”?
Menghitung total berjalan terlebih dahulu satu kali Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Membangun Array Jumlah Awalan” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Membangun Array Jumlah Awalan
- Menjumlahkan Rentang Apa Pun dengan Pengurangan
- Menghitung Subarray dengan Jumlah Target
- Array Selisih untuk Pembaruan Rentang