Alt sorgu sorguları

Question

Bu programlama sorununu çözmeye çalışıyordum. Bir dizi sayı ve bazı sorgular verildiğinde,

. Her bir sorgu size a, b, c olmak üzere üç sayı verir ve a'dan a'ya eşit veya daha küçük olan indeks a'dan indise b (her ikisi de dahil olmak üzere) tüm öğelerin toplamını yanıtlamanızı ister. örneğin

:

Verilen dizi: {2,4,6,1,5,1,6,4,5,4}

3 sorgular cevaplanması gereken edilir:

> ans = 5, yani {4 + 1}

1 5 3 - -> ans = 3, yani {2 + 1}

4 5 1 -> ans = 1

her 2 4 4 dizideki değer 10^5'den küçüktür, dizi uzunluğu ve sorgu sayısı 10^5

'a kadar olabilir. Yaptığım şey, sorguları sıralamak için Mo'nun algoritmasını (Kare kök ayrıştırma) kullanmış ve Tüm değerlerden daha az olan öğelerin birikimli toplamını 1-10^5 arasında saklamak için bir ikili dizinli ağaç ve sorgulardan sorgular için bir güncelleştirme yapıldı. Bu algoritma ile çözümümün genel karmaşıklığı O (q * sqrt (N) * log (N)) ama yeterince hızlı değil. Daha iyi bir algoritma arıyordum. Sorguların karekök ayrışmasının işe yaramayacağını düşünüyorum. Bu sorunu çözmek için daha iyi bir algoritma var mı?

Bazı veri yapısının farkında olmadığım bu sorunu çözüp çözemeyeceğini merak ediyordum?

Answer 1

Diğer şekilde başka bir şekilde deşifre edebilirsiniz. Yani, yarım dizilerden oluşan bir ağaç oluşturun (bu, (n n alan)). Her alt diziyi sıralayın ve bunun için birikimli bir toplam dizi oluşturun. Şimdi sorgularının her (n her alt dizisinde kümülatif toplamı bulmak için Altdizilim ve başka günlüğü n tanımlamak için log) (n log) bulunmaktadır.

Örneğin, orijinal dizi

  5,10,2,7,16,4,8,9 

ilk o zaman bu ağacı

  5,10,2,7,16,4,8,9 
      /  \ 
     5,10,2,7   16,4,8,9 
    / \   / \ 
    5,10  2,7  16,4  8,9 
    /\ /\ /\  /\ 
    5 10 2 7 16 4  8 9 

inşa sorgu demek cevap vermek istiyorum Şimdi eğer hepsini

  2,4,5,7,8,9,10,16 
      /  \ 
     2,5,7,10   4,8,9,16 
    / \   / \ 
    5,10  2,7  4,16  8,9 
    /\ /\ /\  /\ 
    5 10 2 7 16 4  8 9 

sıralamak ise (1,6,8) (endeksler 0-tabanlıdır) (1,6) aralığını ikili altinterkalara (1) (2,3) (4,5) (6) ayırırsınız. en fazla 2 log n) sonra her birinin cevabını ayrı olarak bulun (0 (1) = {10}, 9 için (2,3) = {2,7}, 4 için (4,5)) = {16,4}, 8 için (6) = {8}) ve özetleyin.

İlk ağaç bina kez çiftleri (değer, indeks) sıralamak if (n günlüğüne n) yapılır ve sonra sadece sıralanan dizi günlüğüne n (bir kez her ağacın düzeyi için) süreleri ve kopya üzerinden geçmek edilebilir ilgili düğümlere değerler.