Hitung ulang sekali saja
Kenapa ini penting "Total X antara dua titik" adalah salah satu pertanyaan paling umum dalam kode pelaporan. Menjawab setiap pertanyaan dengan menjumlahkan rentang itu lambat; menyimpan total untuk setiap titik bisa terlalu besar. Ada jalan tengah di antara keduanya.
A menyimpan 60.000 hari penjualan di toko berbayar, diberikan kepadamu sebagai Tape. Keuangan mengirimkan satu paket berisi 50 pertanyaan sekaligus: "total penjualan dari hari a sampai hari b". Kamu berjalan di worker kecil dengan sedikit memori sisa.
Total berjalan (prefix sum): jumlah dari semua hal sebelum posisi tertentu. Total sebuah window adalah total berjalan di akhirnya dikurangi total berjalan di awalnya.
sales = [5, 1, 4, 2, 8]
# running totals before each position: 0, 5, 6, 10, 12, 20
# window (1, 4) = 12 - 5 = 7Tulis range_totals(tape, queries). tape adalah Tape penjualan harian (bilangan bulat). queries adalah daftar pasangan (start, end) dengan 0 <= start <= end <= len(tape). Kembalikan daftar dengan total tape[start:end] untuk setiap kueri, sesuai urutan yang diberikan. Budgets: baca pita maksimal satu kali (60,100 bacaan untuk 60,000 hari dan 50 kueri), dan gunakan maksimal 100,000 byte memori kerja saat fungsi kamu berjalan (diukur dengan tracemalloc; total berjalan untuk setiap hari, atau bahkan daftar biasa dari 60,000 nilai, jauh di atas 100,000 byte). Semua pertanyaan datang bersamaan, sebelum kamu membaca data.
Ada masalah di pelajaran ini? Laporkan · Tanya tentang pelajaran ini
Latihan ini akan segera dibuka
Selesaikan pelajaran sebelumnya agar pelajaran ini terbuka. Seluruh kursus ini gratis, tidak butuh akun, dan kamu bisa baca pelajaran ini sekarang.
Browser ini memblokir cookie untuk learn.floati.life, jadi pelajaran yang sudah kamu selesaikan di sini tidak bisa dibuka berurutan. Izinkan cookie untuk situs ini dan muat ulang.