Suche nach einem Maximalwert kleiner als V in einem Array aus K linearen Funktionen

Question

Entschuldigung für die mangelnde Klarheit in der Fragenbeschreibung.

Ich habe ein Array bestehend aus Länge $Und$ bestehend aus $K$ lineare Subarrays.Wir definieren ein lineares Subarray als zusammenhängendes Subarray des Arrays $[l,r]$ wo $ A [ich]-EIN [ich-1] = C $, eine Konstante für alle $l.(Beachten: $C$ kann für verschiedene Subarrays unterschiedlich sein;die Elemente des Arrays sind ganze Zahlen.) Bitte beachten Sie, dass die linearen Subarrays sind nicht disjunkt (es gibt einen Elementschnittpunkt zwischen einem beliebigen Paar benachbarter linearer Subarrays).Zum Beispiel hat [1,3,5,4,3,2] zwei lineare Subarrays:[1,3,5] und [5,4,3,2].[1,3,5,1,2,3] hätte drei:[1,3,5], [5,1], [1,2,3].

Ich möchte mehrere Abfragen für den Maximalwert finden, der kleiner als ein abgefragter Wert ist $V$, in $o(K)$ und $a(N)$ zeit pro Abfrage, mit $o(K^2)$ und $a(N)$ Vorverarbeitung.(Angenommen, das Array wurde bereits in Bezug auf die gespeichert.) K lineare Subarrays, vielleicht in Bezug auf die Konstante C und Länge jedes Subarrays, wobei die Subarrays geordnet sind.Daher erhalten Sie das Array mit den Start- und Endpunkten aller linearen Subarrays sowie der linearen Konstante C, wie zuvor beschrieben.Man muss also die linearen Subarrays überhaupt nicht ableiten.) Andernfalls wäre ein Nachweis (formell oder nicht), dass dies nicht möglich ist, erwünscht.

Natürlich erfüllt ein ausgewogener binärer Suchbaum (BBST) oder einfaches Sortieren den Zweck, aber es erfordert $O(nicht anmelden)$ vorverarbeitung, das ist zu viel.Die Überprüfung des größten gültigen Werts in jedem Subarray dauert $O(K)$ pro Abfrage, was wieder zu viel ist.Wäre es vielleicht möglich, beides zu kombinieren?

Randomisierte Algorithmen sind in Ordnung, solange sie immer die richtige Antwort liefern und im Durchschnittsfall schnell genug arbeiten, obwohl deterministische Algorithmen bevorzugt werden.

Vielen Dank für alle Antworten.Ich habe mich gefragt, ob die Frage vielleicht recherchiert wurde?Es scheint kein zu dunkles Thema zu sein, aber leider war meine Suche nicht kompetent genug.

BEARBEITEN:Eine Methode, die nützlich erscheint.

Hier war meine Denkweise, nachdem ich die Frage gestellt hatte;Ich frage mich, ob das irgendwie helfen würde.Es nutzt auch die Idee von Modulo.Initialisieren V=0, und erlaube, dass jedes lineare Subarray als gespeichert wird L,R;wo L ist der Minimalwert des Subarrays und R ist der Maximalwert.Wenn wir eine Anfrage erhalten für V, schließen wir irgendwie Elemente aus, wo L>V und R<V (vielleicht durch Verwendung mehrerer Dimensionen?) Eine ergänzende Datenstruktur speichert die minimale theoretische Differenz des Elements im Array, die ungefähr so aussieht L - V mod c[i].Im Wesentlichen müssen wir jetzt in der Lage sein, eine Bereichserweiterung für diese Datenstruktur auszuführen, aber wenn der Wert eines Elements wird <0 oder >=c[i] es muss zurückgesetzt werden (zB.wenn ein Element mit c [i] = 5 gleich -1 wird, wird es auf 4 zurückgesetzt;wenn ein Element, das mit demselben c [i] gleich 6 wird, auf 1 zurückgesetzt würde);führen Sie auch Bereichsminimumabfragen aus.

Wenn eine solche Datenstruktur erstellt werden kann, ist das Problem gelöst.Das Problem ist das Modulo, da Bereichserweiterungen und Bereichsminimumabfragen einfach mit einem Segmentbaum und verzögerter Weitergabe durchgeführt werden können;sowie die Nichteinbeziehung bestimmter Elemente.

Answer 1

Es kann nicht garantiert werden, dass der Maximalwert kleiner als ein abgefragter Wert ist $V$ in $o(K)$ zeit mit Vorverarbeitung in $a(N)$ Zeit.

Dies ist im folgenden Extremfall leicht zu erkennen.Lassen $Ein$ sei ein beliebiges Array von $Und$ Ganzzahlen, die sich aus Folgendem zusammensetzen $K= N-1$ lineare Subarrays.

• das Subarray $EIN [0], EIN [1]$ mit $ C = EIN [1]-EIN [0]$.
• das Subarray $EIN [1], EIN [2]$ mit $ C = EIN [2]-EIN [1]$.
• $\dots$
• das Subarray $ EIN [N-2], EIN [N-1]$ mit $ C = EIN [N-1]-EIN [N-2]$.

Mit $a(N)$ zeitvorverarbeitung und $a(K)=A(N)$ zeitverarbeitung wird ein Algorithmus nicht einmal in der Lage sein, eine Zahl einzulesen $Ein$ wenn $Und$ ist groß genug.(Tatsächlich sind die meisten Zahlen in $Ein$.) Also, für einen abgefragten Wert $q$, wird der Algorithmus das nicht erkennen $q+1$ erscheint in $Ein$.

(Die obige Erklärung könnte strenger formuliert werden, beispielsweise unter Verwendung der formalen Methode des Gegners und eines genau definierten Berechnungsmodells.)

---

Es sieht so aus, als ob die interessantere Frage sein sollte, ob es einen Algorithmus mit gibt $o(N\log N)$ vorverarbeitung und $o(K)$ pro Abfrage.Oder ob es einen Algorithmus mit gibt $a(N)$ vorverarbeitung und $o(K)$ pro Abfrage angegeben $K=o(N)$.Das klingt sowieso nach einer anderen Frage.