Range Sum Query
Hiç değişmeyen bir tamsayı dizisi nums ve bir queries listesi alırsınız. Her sorgu, 0 tabanlı indekslerden oluşan bir [left, right] çiftidir ve nums[left] + nums[left+1] + ... + nums[right] toplamını ister; her iki uç da dahildir. Yanıtları, sorgularla aynı sırada döndürün.
Fonksiyon
- numsinteger-array
- tamsayı dizisi; her sorgu için aynıdır
- 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 sorgu[left, right]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'dan 2'ye kadar olan indekslerde
3 + (-2) + 5 = 6bulunur. 1'den 4'e kadar olan indekslerde-2 + 5 + 1 + (-4) = 0bulunur.[3, 3]aralığı, tek bir değer olan1'i içerir.
- 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ı
2 + 7 + 1 + 8 = 18, son iki değerin toplamı1 + 8 = 9, yalnızca 0. indeksin değeri2ve 1 ile 2. indekslerin toplamı7 + 1 = 8.
Gönderirken +14 gizli test
Ek soru
Artık sayılar bir ızgara oluşturuyor ve her sorgu, iki köşesi verilen bir dikdörtgenin toplamını soruyor. Her sorguyu sabit sayıda işlemle yanıtlamak için önek toplamlarını nasıl genişletirdin?
İ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ık 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
Bir aralık bir döngüdür. Sorun, bunların sayısıdır: her sorgu dizinin çoğunu kapsayabilir, bu yüzden her birini ayrı ayrı toplamak aynı toplamaları tekrar tekrar yapar. Her şeyi bir kez önek toplamlarında topla, böylece her aralık tek bir çıkarma işlemine dönüşür.
Her aralığı topla
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her sorguyu ayrı ayrı yanıtla: toplamı 0'dan başlat, nums[left] ile nums[right] arasındaki değerleri topla ve sonucu kaydet. [3, -2, 5, 1, -4, 6] dizisindeki [1, 4] için sonuç -2 + 5 + 1 + (-4) = 0 olur.
Bu doğrudur ve tek bir sorgu için yapabileceğinin en iyisidir: aralıktaki her değeri bir kez okumak zorundasın. Maliyet, işlemin tekrarlanmasından kaynaklanır. Bir sorgu en fazla n değer kapsayabilir; bu nedenle q sorgu en fazla n × q toplama işlemi gerektirir. n = 10^4 ve dizinin büyük bölümünü kapsayan 1500 sorgu için bu yaklaşık 1.3 × 10^7 toplama işlemidir; bunların neredeyse tamamı, önceki bir sorgu için yapılan işlemlerin tekrarıdır.
Yanıt listesinin yanı sıra tek bir toplam tuttuğundan, ek alan kullanımı O(1)'dir.
Algoritma
- Boş bir yanıt listesi oluşturun.
- Her
[left, right]sorgusu içintotal = 0olarak ayarlayın. leftilerightarasındaki (her ikisi de dahil) heriiçinnums[i]değerinitotaldeğerine ekleyin.totaldeğerini yanıtlara ekleyin ve son sorgudan sonra bunları döndürün.
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; boş başlangıç için prefix[0] = 0. [3, -2, 5, 1, -4, 6] için prefix = [0, 3, 1, 6, 7, 3, 9] elde edilir. Her öğe, kendisinden önceki öğeye bir değerin eklenmesiyle oluşur; dolayısıyla tüm dizi için n toplama işlemi gerekir.
[left, right] aralığı, right indeksine kadar ve bu indeks dâhil olan her şeyden left indeksinden önceki her şeyin çıkarılmasıdır. Yani prefix[right+1] - prefix[left]. [1, 4] için: prefix[5] - prefix[1] = 3 - 3 = 0. [0, 2] için: prefix[3] - prefix[0] = 6 - 0 = 6. Baştaki 0, indeks 0'dan başlayan bir aralığın özel bir durum olmadan çalışmasını sağlar.
Diziyi oluşturmanın maliyeti O(n), her sorgunun maliyeti ise tek bir çıkarma işlemidir; dolayısıyla toplam süre O(n + q) ve ek alan O(n) olur. Buradaki hiçbir önek toplamı 10^4 × 10^4 = 10^8 değerini aşmaz, bu nedenle 32 bitlik tam sayılar yeterlidir.
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
Buradaki hataların neredeyse tamamı, indeksin bir kaymış olmasından kaynaklanıyor.
prefix[right] - prefix[left]yazmak.prefix[0] = 0olduğundanums[right]dışarıda kalır; bu nedenle[3, 3]aralığı, 3. indeksteki değer yerine0döndürür.prefixdizisininumsile aynı uzunlukta oluşturmak, böyleceprefix[i]değerininnums[i]değerini de içermesi. Bu durumda0'dan başlayan bir aralık içinprefix[left-1]gerekir; bu da sınırların dışındadır ve Python'da sessizce son öğeyi okur. Baştaki fazladan0bu özel durumu ortadan kaldırır.- Kaba kuvvet yönteminde döngüyü
i < rightkoşulunda durdurmak. Aralığın her iki ucu da dahildir. - Lua ve R'nin 1'den saymaya başladığını unutmak. 0 tabanlı
[left, right]sorgusu bu dillerdenums[left+1]ilenums[right+1]arasını kapsar ve önek farkı da aynı şekilde kayar. - Değerler veya uzunluklar büyüdüğünde 32 bitlik toplam kullanmak. Buradaki en büyük toplam
10^8, ancak10^9'a yakın değerlerde önek toplamı hızla taşar; 64 bitlik bir dizi güvenli varsayılandır.
Sıkça sorulan sorular4
Önek toplam dizisi nedir?
Her bir girdinin bir konumdan önceki tüm değerlerin toplamı olduğu bir dizidir: prefix[i] = nums[0] + ... + nums[i-1]; prefix[0] = 0. Bunu tek geçişte oluşturursun ve sonrasında herhangi bir [left, right] aralığının toplamı tek bir çıkarma işlemiyle 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); böylece q sorgu için toplam O(n + q). Her aralığı doğrudan toplamak sorgu başına en fazla O(n) maliyetlidir; bu da toplamda O(n·q) eder.
Önek dizisinin neden nums'tan bir fazla girdisi var?
Ekstra prefix[0] = 0, dizinin boş başlangıcını temsil eder. Bununla birlikte, 0 dizininde başlayan aralıklar da dahil olmak üzere her aralık aynı formülü kullanır: prefix[right+1] - prefix[0]. Bu olmadan, left = 0 için ayrı bir koşul gerekir.
Ya sorgular arasında dizi değişebiliyorsa?
Bu durumda önek dizisi yanlış bir araçtır, çünkü tek bir güncelleme kendisinden sonraki tüm toplamları kaydırır ve bunları düzeltmek O(n) maliyetlidir. Bir Fenwick ağacı veya segment ağacı, hem güncellemeyi hem de aralık toplamını O(log n) sürede işler. Dizi hiç değişmiyorsa basit önek toplamları daha hızlıdır ve daha az yer kaplar.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def sumRange(nums, queries):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Beklenen
[6, 0, 1]