Subarray Abfragen

Also habe ich versucht, dieses Programmierproblem zu lösen.Subarray Abfragen

Angesichts einer Reihe von Zahlen und einige Abfragen. Jede Abfrage gibt Ihnen drei Zahlen a, b, c und fordert Sie auf, die Summe aller Elemente von Index a bis Index b (beide eingeschlossen) zu beantworten, die kleiner oder gleich c sind.

zum Beispiel:

Gegeben Array: {2,4,6,1,5,1,6,4,5,4}

3 Anfragen zu beantworten sind:

2 4 4 -> am = 5 dh {4 + 1}

1 5 3 -> am = 3, dh {2 + 1}

4 5 1 -> 1 am =

jeweils Wert im Array ist weniger als 10^5, die Länge des Arrays und die Anzahl der Abfragen könnte reichen bis 10^5

Hier ist, was ich tat ich verwendet Mo's Algorithmus (Square Root Decomposition), um die Abfragen zu sortieren, und erstellt Ein binärer indizierter Baum, um die kumulative Summe der Elemente unter allen Werten von 1-10^5 zu speichern und eine Aktualisierung von Abfragen zu Abfragen durchzuführen. Mit diesem Algorithmus ist die Gesamtkomplexität meiner Lösung O (q * sqrt (N) * log (N)), aber es ist nicht schnell genug. Ich suchte nach einem besseren Algorithmus. Ich denke, Wurzelzerlegung von Abfragen würde nicht funktionieren. Gibt es einen besseren Algorithmus, um dieses Problem zu lösen?

Ich fragte mich, ob eine Datenstruktur dieses Problem lösen könnte, das mir nicht bewusst ist?

Quelle

2017-06-06 ash

Sie meinen "a", "b", "c" sind Indizes? Und verwenden Sie nullbasierte Indexierung? – Bahrom

@Bahrom a und b sind "1" -basierte Indizes, c ist eine Zahl. – ash

Sie können es anders herum zerlegen. Nämlich, baue einen Baum von Halb-Arrays (dies ist (n log n) Raum). Sortieren Sie jedes Unterfeld und erstellen Sie ein kumulatives Summenfeld dafür. Jetzt sind Ihre Anfragen jeder (log n die Sub-Arrays zu identifizieren und andere Protokoll n die kumulative Summe in jedem Sub-Array zu finden) (n log).

Zum Beispiel, wenn Ihre ursprüngliche Array ist

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

Sie erste Baum bauen

  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

dann sortieren sie alle

  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

Nun, wenn Sie Anfrage beantworten wollen sagen (1,6,8) (Indizes sind 0-basiert) Sie zerlegen das (1,6) -Intervall in binäre Teilintervalle (1) (2,3) (4,5) (6) (es gibt nicht mehr als 2 log n von denen) dann finden Sie die Antwort für jeden separat (0 für (1) = {10}, 9 für (2,3) = {2,7}, 4 für (4,5) = {16,4}, 8 für (6) = {8}) und summiere sie.

Initial Baum Gebäude kann in (n log n) durchgeführt werden, wenn Sie Paare (Wert, Index) sortieren einmal und dann übergeben Sie einfach über die sortierten Array log n-mal (einmal für jeden Baumebene) und Kopie die Werte zu ihren jeweiligen Knoten.

Quelle

2017-06-07 06:35:51

In Bezug auf die Implementierung können Sie eine rekursive Funktion für den Baum definieren, die (1) nur die Summe des aktuellen Knotens zurückgibt, wenn sie vollständig im Intervall enthalten ist. (2) gibt das Ergebnis der Funktion entweder auf dem linken oder rechten Kind zurück Summe, wenn das Intervall nur entweder auf der linken oder der rechten Seite ist, (3) gibt die Summe des Funktionsaufrufs sowohl für das linke als auch das rechte Kind zurück, wenn das Intervall auf beiden Seiten ist, dh über die Mitte hinausgeht. Es scheint einfacher zu sein als zu versuchen, das Intervall am Anfang vollständig zu teilen. Das scheint nur O (log n) pro Abfrage zu sein. – Dukeling

Können Sie näher ausführen, wie Sie die tatsächliche Summe der Elemente kleiner oder gleich c (in O (log n)) finden? Eine Möglichkeit wäre, eine kumulative Summe für jeden Knoten zu speichern und dann innerhalb dieses Knotens eine binäre Suche durchzuführen, um die anwendbare Summe zu finden. – Dukeling

@Dueling ja das ist genau das, was ich im Sinn hatte –

Subarray Abfragen

Antwort

Verwandte Themen