Menjumlahkan Rentang Apa Pun dengan Pengurangan
Menjawab range[l..r] dalam waktu konstan
Menjumlahkan Rentang Apa Pun dengan Pengurangan adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 2 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.
Manfaat Sebenarnya
Membangun larik jumlah prefiks hanyalah persiapan. Sekarang tibalah keajaibannya: menjawab jumlah rentang apa pun dengan satu pengurangan. ⚡
Gagasan Inti
Jumlah rentang hanyalah satu total besar dikurangi total yang lebih kecil. Mengurangkan dua nilai prefiks akan menghapus semua hal di luar rentang Anda dengan rapi.
Rumus
Untuk menjumlahkan elemen dari l hingga r, ambil prefix[r + 1] lalu kurangi prefix[l]. Rumus tunggal ini berlaku untuk setiap rentang.
range_sum = prefix[r + 1] - prefix[l]Mengapa Ini Berhasil
prefix[r + 1] berisi semua nilai hingga r, sedangkan prefix[l] berisi semua nilai sebelum l. Selisih keduanya menyisakan tepat bagian tengah.
Contoh Perhitungan
Untuk [3, 1, 4], prefiksnya adalah [0, 3, 4, 8]. Untuk menjumlahkan indeks 1 hingga 2, hitung 8 dikurangi 3, yang menghasilkan 5. Hasil itu sama dengan 1 ditambah 4.
Query Waktu Konstan
Setiap query hanya berupa satu pengurangan, sehingga berjalan dalam O(1). Seribu query memiliki biaya per query yang sama dengan satu query.
Perhatikan Kesalahan Satu Posisi
Kesalahan yang paling umum adalah indeks di batas atas. Dengan angka nol di awal, Anda selalu menggunakan prefix[r + 1], bukan prefix[r]. Perhatikan batas tersebut.
Inklusif vs Eksklusif
Tentukan sejak awal apakah r disertakan. Rumus ini memperlakukan rentang sebagai inklusif pada l dan r, seperti yang diharapkan dalam sebagian besar soal kontes.
Bungkus dalam Fungsi
Fungsi pembantu kecil membuat logika Anda mudah dibaca dan menempatkan semua indeks di satu tempat. Gunakan fungsi pembantu ini alih-alih menulis perhitungannya langsung.
def query(l, r):
return prefix[r + 1] - prefix[l]Tangani Seluruh Larik
Untuk menjumlahkan seluruh larik, gunakan l sama dengan 0 dan r sama dengan n dikurangi 1. Rumusnya menghasilkan prefix[n], yaitu total keseluruhan.
Di Mana Ini Unggul
Setiap kali sebuah soal mengajukan banyak pertanyaan jumlah rentang pada larik tetap, jumlah prefiks mengubah loop O(n) per query menjadi jawaban seketika.
Pemeriksaan Cepat
Anda ingin menghitung jumlah indeks l hingga r secara inklusif.
Ringkasan
Sekarang Anda dapat menjawab jumlah rentang apa pun dalam O(1) dengan prefix[r + 1] dikurangi prefix[l]. Perhatikan offset angka nol di awal agar kode Anda bebas bug. ✅
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Menjumlahkan Rentang Apa Pun dengan Pengurangan” gratis?
Ya — teks lengkap “Menjumlahkan Rentang Apa Pun dengan Pengurangan” 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 “Menjumlahkan Rentang Apa Pun dengan Pengurangan”?
Menjawab range[l..r] dalam waktu konstan 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 2 dari 4.
Berapa lama pelajaran “Menjumlahkan Rentang Apa Pun dengan Pengurangan” 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