Wie kann man feststellen, wie viele Elemente eines Bereichs innerhalb eines anderen gegebenen Bereichs liegen?

Question

Ich brauche eine wenig Hilfe, etwas zu versuchen, herauszufinden,:

eine Folge von ungeordneten Zahlen Given (weniger als 15.000) - A - ich Q beantworten muss fragt (Q < = 100000) von der Form i, j, x, y, die als die folgenden übersetzen:

wie viele Zahlen im Bereich [i, j] aus A sind größer (oder gleich) als x aber kleiner als y mit allen Zahlen in t Die Sequenz ist kleiner als 5000.

Ich habe den Eindruck, dass dies etwas wie O (logN) erfordert, wegen der großen Länge der Sequenz und dies hat mich über BIT (binäre indizierte Bäume - wegen der Abfragen) nachdenken lassen 2D BIT ist zu groß und benötigt viel Zeit, um selbst auf der Update-Seite zu laufen. Die einzige Lösung, die ich hier sehen kann, sollte 1D BIT oder Segment Trees sein, aber ich kann mir nicht vorstellen, wie man eine Lösung basierend auf diesen Datenstrukturen ausarbeitet. Ich habe versucht, die Positionen in der geordneten Menge von Zahlen zu behalten, aber ich kann nicht herausfinden, wie man ein BIT erstellt, das auf Anfragen der gegebenen Form antwortet.

Auch der Algorithmus sollte wie 500ms für die gegebenen Grenzen passen. Edit 1: 500ms für alle Operationen auf Vorverarbeitung und die Beantwortung der Anfragen

EDIT 2: Wo i, j sind Positionen des ersten und letzten Elements in der Sequenz A für Elemente größer als x zu betrachten und kleiner als y

EDIT 3: Beispiel: mit 1, 3, 2, 4, 6, 3 und Abfrage-1, 4, 3, 5 so zwischen den Positionen 1 und 4 (einschließlich) sind 2 Sei Elemente (3 und 4) größer (oder gleich) als 3 und kleiner als 5

Vielen Dank im Voraus! PS: Entschuldigung für das schlechte Englisch!

Answer 1

Implementieren Sie die 2D-Bereichszählung, indem Sie ein BIT-organisiertes Array von sortierten Subarrays erstellen. Zum Beispiel auf der Eingangs

[1, 3, 2, 4, 6, 3] 

das Orakel würde

[[1] 
,[1, 3] 
,[2] 
,[1, 2, 3, 4] 
,[6] 
,[3, 6] 
]. 

Die Raumnutzung ist O (N log N) (hoffentlich gut) sein. Die Konstruktion braucht O (N log N) Zeit, wenn Sie vorsichtig sind, oder O (N log^2 N) Zeit, wenn nicht (kein Grund für Ihre Anwendung zu sein).

Um eine Abfrage mit Maximalwerten für Sequenzindex und -wert zu beantworten (vier davon können zum Beantworten der Eingabeabfragen verwendet werden), führen Sie die BIT-Leseprozedur für den maximalen Index aus. Verwenden Sie die Binärsuche im Array, um die Anzahl zu zählen Elemente, die den Maximalwert nicht überschreiten. Die Abfragezeit ist O (log^2 N).