Range Sum Query
Hiç değişmeyen bir tamsayı dizisi nums ve bir queries listesi alırsın. Her sorgu, 0 tabanlı indekslerden oluşan bir [left, right] çiftidir ve nums[left] + nums[left+1] + ... + nums[right] toplamını sorar; her iki uç da dahildir. Yanıtları sorgularla aynı sırada döndür.
Fonksiyon
- numsinteger-array
- tamsayı dizisi, her sorgu için aynı
- queriesinteger-2d-array
- toplanacak aralıklar; her biri left ≤ right koşulunu sağlayan bir [left, right] çifti
- Döndürürinteger-array
- sorgu sırasına göre, her sorgu için bir tane olmak üzere her aralığın toplamı
Kısıtlar
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthher[left, right]sorgusu için
Örnekler
- Girdi
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- Çıktı
- [6, 0, 1]
- Açıklama
- 0 ile 2 arasındaki indekslerde
3 + (-2) + 5 = 6bulunur. 1 ile 4 arasındaki indekslerde-2 + 5 + 1 + (-4) = 0bulunur.[3, 3]aralığı, tek bir değer olan1'dir.
- Girdi
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- Çıktı
- [18, 9, 2, 8]
- Açıklama
- Dizinin tamamının toplamı
18, son iki değerin toplamı1 + 8 = 9, yalnızca 0. indeksin değeri2ve 1'den 2'ye kadar olan indekslerin toplamı7 + 1 = 8eder.
Ek soru
Sayılar bir ızgara oluşturuyorsa ve her sorgu bir dikdörtgenin toplamını istiyorsa, her sorguyu sabit zamanda yanıtlamak için önek toplamlarını nasıl genişletirsin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Birçok sorgu neredeyse aynı değerleri kapsar. Herhangi bir sorguyu okumadan önce hangi işi bir kez yapabilirsin?
Her
iiçin ilkideğerin toplamını bilseydin, bir aralığın toplamı bu toplamların ikisinin farkı olurdu.prefixdizisiniprefix[0] = 0veprefix[i+1] = prefix[i] + nums[i]ile oluştur. Ardından her[left, right]sorgusuprefix[right+1] - prefix[left]olur.
Çözüm
Tek bir aralık bir döngüdür, ancak her sorgu dizinin büyük bölümünü kapsayabilir; bu nedenle her birini ayrı ayrı toplamak aynı toplama işlemlerini tekrarlar. Diziyi bir kez toplayarak önek toplamlarını oluştur ve her aralık tek bir çıkarma işlemine dönüşsün.
Her aralığı topla
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her sorgu için nums[left] ile nums[right] arasındaki değerleri toplama ekleyin. Bu doğrudur çünkü aralıktaki her değeri okur ve tek bir sorgu için yapabileceğiniz en iyi şey budur. Bir sorgu n değere kadar kapsayabilir; dolayısıyla q sorgu en fazla n × q toplama işlemine mal olur: n = 10^4 ve q = 1500 olduğunda 1.5 × 10^7; bunların neredeyse hepsi tekrar eden işlemlerdir.
Algoritma
- Boş bir yanıt listesi oluştur.
- Her
[left, right]sorgusu içintotal = 0olarak ayarla. leftilerightarasındaki (ikisi de dahil) heriiçinnums[i]değerinitotaldeğerine ekle.totaldeğerini yanıt listesine ekle ve son sorgudan sonra yanıtları döndür.
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 answersÖnek toplamları
Sezgi
prefix[i], ilk i değerin toplamı olsun ve prefix[0] = 0 olsun. [3, -2, 5, 1, -4, 6] için sonuç [0, 3, 1, 6, 7, 3, 9] olur.
[left, right] aralığı, right indeksine kadar olan her şeyden left indeksinden önceki her şeyi çıkarmaktır: prefix[right+1] - prefix[left]. [1, 4] için bu, prefix[5] - prefix[1] = 3 - 3 = 0 olur. Baştaki 0, 0 indeksinde başlayan bir aralığın da aynı formülü kullanmasını sağlar. n toplama işleminden oluşan tek bir geçiş diziyi oluşturur ve ardından her sorgu tek bir çıkarma işlemidir.
Algoritma
prefixdizisinin+1uzunluğunda oluştur veprefix[0] = 0olarak ayarla.0ilen-1arasındaki heriiçinprefix[i+1] = prefix[i] + nums[i]olarak ayarla.- Her
[left, right]sorgusu içinprefix[right+1] - prefix[left]değerini yanıtlara ekle. - Yanıtları döndür.
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]
Tuzaklar ve uç durumlar
prefix[right] - prefix[left]yazmak.prefix[0] = 0olduğundanums[right]dışarıda kalır; bu nedenle[3, 3]aralığı1yerine0döndürür.prefix'inumsile aynı uzunlukta oluşturmak; böyleceprefix[i],nums[i]değerini de içerir. 0'dan başlayan bir aralık içinprefix[-1]gerekir; ancak bu dizinin sınırları dışındadır ve Python sessizce son girdiyi okur.- Kaba kuvvet döngüsünü
i < rightkoşulunda durdurmak. Her iki uç da aralığa dahildir; bu nedenle[3, 3]hiçbir şeyi toplamaz. - 1'den saymaya başlayan Lua ve R'de, 0 tabanlı
[left, right]sorgusunums[left+1]ilenums[right+1]arasını kapsar ve prefix indeksleri de aynı şekilde kayar.
Sıkça sorulan sorular3
Önek toplam dizisi nedir?
Her bir girdinin, bir konumdan önceki tüm değerlerin toplamı olduğu bir dizi: prefix[i] = nums[0] + ... + nums[i-1], prefix[0] = 0 olacak şekilde. Bu diziyi tek geçişte oluşturursun; ardından herhangi bir [left, right] aralığının toplamı prefix[right+1] - prefix[left] olur.
Önek toplamlarıyla aralık toplamı sorgularının zaman karmaşıklığı nedir?
Önek dizisini bir kez oluşturmak için O(n), ardından sorgu başına O(1); dolayısıyla q sorgu için toplam O(n + q). Her aralığı doğrudan toplamak, sorgu başına O(n)'e kadar, toplamda ise O(n·q) maliyete neden olur.
Dizi sorgular arasında değişebilirse ne olur?
Bu durumda önek dizisi yanlış araçtır, çünkü bir güncelleme kendisinden sonraki tüm toplamları kaydırır ve bunları düzeltmek O(n) maliyetlidir. Fenwick ağacı veya segment ağacı, hem güncellemeyi hem de aralık toplamını O(log n) sürede işler.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def sumRange(nums, queries):
# Kodu buraya yazınTest #1
Test #2
Argümanlar
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Beklenen Çıktı
[6, 0, 1]