Range Sum Query
Kamu mendapatkan array bilangan bulat nums yang tidak pernah berubah dan list queries. Setiap kueri berupa pasangan [left, right] indeks berbasis 0, dan meminta hasil nums[left] + nums[left+1] + ... + nums[right], dengan kedua ujung disertakan. Kembalikan jawabannya dalam urutan yang sama dengan kueri.
Fungsi
- numsinteger-array
- array bilangan bulat, sama untuk setiap query
- queriesinteger-2d-array
- rentang yang dijumlahkan, masing-masing berupa pasangan [left, right] dengan left ≤ right
- Mengembalikaninteger-array
- jumlah setiap rentang, satu untuk tiap query, sesuai urutan query
Batasan
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthuntuk setiap kueri[left, right]
Contoh
- Input
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- Output
- [6, 0, 1]
- Penjelasan
- Indeks 0 sampai 2 berisi
3 + (-2) + 5 = 6. Indeks 1 sampai 4 berisi-2 + 5 + 1 + (-4) = 0. Rentang[3, 3]adalah satu nilai, yaitu1.
- Input
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- Output
- [18, 9, 2, 8]
- Penjelasan
- Seluruh array berjumlah
18, dua nilai terakhir berjumlah1 + 8 = 9, indeks 0 saja berjumlah2, dan indeks 1 hingga 2 berjumlah7 + 1 = 8.
Pertanyaan lanjutan
Jika angka-angka membentuk kisi dan setiap query meminta jumlah dalam sebuah persegi panjang, bagaimana kamu akan memperluas jumlah prefiks untuk menjawab setiap query dalam waktu konstan?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Banyak kueri mencakup nilai yang hampir sama. Pekerjaan apa yang bisa kamu lakukan sekali saja, sebelum membaca kueri apa pun?
Jika kamu mengetahui jumlah dari
inilai pertama untuk setiapi, rentang adalah selisih antara dua jumlah tersebut.Buat
prefixdenganprefix[0] = 0danprefix[i+1] = prefix[i] + nums[i]. Lalu, setiap kueri[left, right]adalahprefix[right+1] - prefix[left].
Solusi
Satu rentang adalah perulangan, tetapi setiap query dapat mencakup sebagian besar array, sehingga menjumlahkan tiap rentang secara terpisah akan mengulangi penjumlahan yang sama. Jumlahkan seluruh array sekali untuk membuat jumlah prefiks, lalu setiap rentang cukup dihitung dengan satu pengurangan.
Jumlahkan setiap rentang
Benar, tetapi tidak selesai pada tes terbesar
Intuisi
Untuk setiap kueri, tambahkan nums[left] hingga nums[right] ke dalam total. Cara ini benar karena membaca setiap nilai dalam rentang tersebut, dan untuk satu kueri, itulah cara terbaik yang bisa kamu lakukan. Satu kueri dapat mencakup hingga n nilai, jadi q kueri memerlukan hingga n × q penjumlahan: 1.5 × 10^7 ketika n = 10^4 dan q = 1500, dan hampir semuanya berulang.
Algoritma
- Buat list jawaban kosong.
- Untuk setiap query
[left, right], tetapkantotal = 0. - Tambahkan
nums[i]ketotaluntuk setiapidarilefthinggaright, termasuk keduanya. - Tambahkan
totalke jawaban, lalu kembalikan semuanya setelah query terakhir.
def sumRange(nums, queries):
answers = []
for left, right in queries:
total = 0
for i in range(left, right + 1):
total += nums[i]
answers.append(total)
return answersJumlah prefiks
Intuisi
Misalkan prefix[i] adalah jumlah dari i nilai pertama, dengan prefix[0] = 0. Untuk [3, -2, 5, 1, -4, 6], hasilnya adalah [0, 3, 1, 6, 7, 3, 9].
Rentang [left, right] adalah jumlah semua nilai hingga indeks right dikurangi jumlah semua nilai sebelum indeks left: prefix[right+1] - prefix[left]. Untuk [1, 4], hasilnya adalah prefix[5] - prefix[1] = 3 - 3 = 0. Angka 0 di awal memungkinkan rentang yang dimulai pada indeks 0 menggunakan rumus yang sama. Satu kali melewati array dengan n penjumlahan akan membentuk array tersebut, lalu setiap kueri hanya memerlukan satu pengurangan.
Algoritma
- Buat
prefixdengan panjangn+1danprefix[0] = 0. - Untuk setiap
idari0hinggan-1, tetapkanprefix[i+1] = prefix[i] + nums[i]. - Untuk setiap kueri
[left, right], tambahkanprefix[right+1] - prefix[left]ke jawaban. - Kembalikan jawaban.
def sumRange(nums, queries):
# prefix[i] is the sum of the first i values, so prefix[0] = 0.
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
# nums[left..right] is the first right+1 values minus the first left values.
return [prefix[right + 1] - prefix[left] for left, right in queries]
Jebakan dan kasus tepi
- Menulis
prefix[right] - prefix[left]. Denganprefix[0] = 0, cara ini tidak menyertakannums[right], sehingga rentang[3, 3]menghasilkan0, bukan1. - Membuat
prefixsepanjangnums, sehinggaprefix[i]menyertakannums[i]. Rentang yang dimulai dari 0 kemudian membutuhkanprefix[-1], yang berada di luar batas, dan Python diam-diam membaca entri terakhir. - Menghentikan perulangan brute force pada
i < right. Kedua ujung rentang disertakan, jadi[3, 3]tidak akan menjumlahkan apa pun. - Di Lua dan R, yang dimulai dari 1, kueri berbasis 0
[left, right]mencakupnums[left+1]hingganums[right+1], dan indeks prefix bergeser dengan cara yang sama.
Pertanyaan yang sering diajukan3
Apa itu array jumlah prefiks?
Array yang setiap entrinya merupakan total semua nilai sebelum suatu posisi: prefix[i] = nums[0] + ... + nums[i-1], dengan prefix[0] = 0. Kamu membangunnya dalam satu lintasan, lalu jumlah rentang mana pun [left, right] adalah prefix[right+1] - prefix[left].
Berapa kompleksitas waktu kueri jumlah rentang dengan jumlah prefiks?
O(n) untuk membangun array prefix sekali, lalu O(1) untuk setiap kueri, jadi O(n + q) untuk q kueri. Menjumlahkan setiap rentang secara langsung membutuhkan hingga O(n) untuk setiap kueri, totalnya O(n·q).
Bagaimana jika array dapat berubah di antara kueri?
Jadi, array prefix bukan alat yang tepat, karena satu pembaruan menggeser semua total setelahnya dan membutuhkan biaya O(n) untuk memperbaikinya. Fenwick tree atau segment tree menangani pembaruan dan penjumlahan rentang dalam O(log n).
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def sumRange(nums, queries):
# Tulis kodemu di siniTes #1
Tes #2
Argumen
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Output yang diharapkan
[6, 0, 1]