So erhöhen Sie alle Werte in einem Array-Intervall um einen bestimmten Betrag

Alle Intervalle in Start- und Ende-Indizes zerlegen: s_i , e_i für das i-te Intervall, das beginnt s_i zu enthalten und endet mit e_i

Sortiere alle s_i -s als ein Array S Sortiere alle e_i -s als Array E

setze increment auf Null Starten Sie einen linearen Scan der Eingabe und fügen Sie jedem einen Zuwachs hinzu. in jeder Schleife, wenn der nächste s_i der aktuelle index inkrement increment ist, wenn der nächste e_i ist index decement increment

Komplexität (ohne nicht inkrementierte Elemente zu überspringen): O(n+m*log(m)) // m ist die Anzahl der Intervalle Wenn n>>m , dann ist es O(n)

Komplexität beim Überspringen von Elementen: O( min( n , \sum length(I_i) ) ) , wo length(I_i)=e_i-s_i

Sie können O (N + M) erhalten. Behalte ein zusätzliches Inkrement-Array B der gleichen Größe von A, das anfänglich leer ist (gefüllt mit 0). Wenn Sie den Bereich (i, j) mit dem Wert k erhöhen müssen, dann tun Sie B [i] + = k und B [j + 1] - = k

Führe jetzt eine partielle Summentransformation in B durch, indem du denkst, dass du von 0 ausgehend indexierst:

Und nun sind die endgültigen Werte von A A [i] + B [i]

Es gibt drei Hauptansätze, die ich mir vorstellen kann:

Ansatz 1

Dies ist der einfachste, bei dem Sie einfach das Array behalten und die naive Sache für die Inkremente tun.

• Pro: Abfrage ist konstante Zeit   
• Nachteile: Inkrement kann lineare Zeit sein (und daher ziemlich langsam, wenn L groß ist)

Ansatz 2

Dieser ist ein wenig komplizierter, aber ist besser, wenn Sie viel inkrementieren wollen.

Speichern Sie die Elemente in einem binären Baum, so dass ein intraoperatives Traversal auf die Elemente in der Reihenfolge zugreift. Jeder Knoten speichert (abgesehen von den normalen linken und rechten Subchildren) auch einen zusätzlichen int addOn , der lautet: "Fügen Sie mich hinzu, wenn Sie einen Knoten in diesem Baum abfragen".

Um Elemente abzufragen, führen Sie die normale binäre Suche nach dem Index durch, um das Element zu finden, wobei Sie alle Werte der Variablen addOn addieren, während Sie fortfahren. Fügen Sie diese zum A[i] am gewünschten Knoten hinzu, und das ist Ihr Wert.

Gehen Sie für Inkremente in den Baum und aktualisieren Sie alle neuen addOns nach Bedarf. Beachten Sie, dass Sie, wenn Sie den inkrementierten Wert zu einem addOn für einen Knoten hinzufügen, ihn nicht für die beiden untergeordneten Elemente aktualisieren. Die Laufzeit für jedes Inkrement ist dann O(log L) , da das einzige Mal, wenn Sie jemals in die Kinder "abzweigen" müssen, wenn das erste oder letzte Element in dem Intervall in Ihrem Bereich ist. Daher verzweigen Sie maximal 2 log L mal und greifen auf einen konstanten Faktor mehr in Elementen zu.

• Pro: Inkrement ist jetzt O (log L), also sind die Dinge jetzt viel schneller als vorher, wenn Sie eine Tonne erhöhen.    
• Nachteile: Abfragen dauern länger (auch O (log L)), und die Implementierung ist viel komplizierter.

Ansatz 3

Verwenden Sie eine Intervallstruktur .

• Pro: Genau wie Ansatz 2 kann dieser viel schneller sein als der naive Ansatz    
• Nachteile: Nicht machbar, wenn Sie nicht wissen, was die Intervalle im voraus sein werden.
  Auch schwierig zu implementieren

Löse das Problem für ein einzelnes Intervall. Dann iteriere über alle Intervalle und wende jeweils die Einzelintervalllösung an. Die beste Datenstruktur hängt von der Sprache ab. Hier ist ein Java-Beispiel:

Natürlich könnten Sie eine Schleife ineinander verschachteln, wenn Sie die Menge an Code reduzieren möchten. Eine Einzelintervall-Methode könnte jedoch auch nützlich sein.

BEARBEITEN

Wenn die Intervalle vorher bekannt sind, können Sie die Dinge etwas verbessern. Sie können die Interval -Struktur ändern, um einen Inkrementbetrag beizubehalten (der Standardwert ist 1). Dann verarbeiten Sie die Menge der Intervalle S wie folgt vor:

1. Initialisiere eine zweite Menge von Intervallen T auf die leere Menge
2. Für jedes Intervall I in S : Wenn ich kein Intervall in T überschneide, füge I hinzu zu T ; Ansonsten:
3. Für jedes Intervall J in T , das I überlappt, entfernen Sie J von T , neue Intervalle bilden K ₁ ... K _n von < em> I und J , sodass es keine Überlappungen gibt ( n kann von 1 bis 3 sein), und fügen Sie K 1 ... K _n bis T

Wenn dies abgeschlossen ist, verwenden Sie die Intervalle in T mit dem früheren Code (wie beschrieben). Da keine Überlappungen vorhanden sind, wird kein Element des Arrays mehr als einmal inkrementiert. Für einen festen Satz von Intervallen ist dies ein konstanter Zeit -Algorithmus, unabhängig von der Array-Länge.

Für N Intervalle kann der Aufspaltungsprozess wahrscheinlich so entworfen werden, dass er in etwas nahe bei O (N log N) abläuft, indem T nach dem Intervallstartindex geordnet gehalten wird. Wenn sich die Kosten jedoch unter vielen Array-Inkrementierungsoperationen amortisieren, ist dies für die Gesamtkomplexität nicht besonders wichtig.

Eine mögliche Implementierung von O (M + N) Algorithmus vorgeschlagen von Adrian Budau