Range Sum Query
Du erhältst ein Array aus Ganzzahlen nums, das sich nie ändert, und eine Liste von queries. Jede Abfrage ist ein Paar [left, right] von 0-basierten Indizes und fragt nach nums[left] + nums[left+1] + ... + nums[right], wobei beide Enden eingeschlossen sind. Gib die Antworten in derselben Reihenfolge wie die Abfragen zurück.
Funktion
- numsinteger-array
- das Integer-Array, das für jede Abfrage gleich ist
- queriesinteger-2d-array
- die zu addierenden Bereiche, jeweils ein Paar [left, right] mit left ≤ right
- Gibt zurückinteger-array
- die Summe jedes Bereichs, eine pro Abfrage, in der Reihenfolge der Abfragen
Einschränkungen
1 ≤ nums.length ≤ 104-104 ≤ nums[i] ≤ 1041 ≤ queries.length ≤ 15000 ≤ left ≤ right < nums.lengthfür jede Abfrage[left, right]
Beispiele
- Eingabe
- nums = [3, -2, 5, 1, -4, 6]queries = [[0, 2], [1, 4], [3, 3]]
- Ausgabe
- [6, 0, 1]
- Erklärung
- Die Indizes 0 bis 2 ergeben
3 + (-2) + 5 = 6. Die Indizes 1 bis 4 ergeben-2 + 5 + 1 + (-4) = 0. Der Bereich[3, 3]ist der einzelne Wert1.
- Eingabe
- nums = [2, 7, 1, 8]queries = [[0, 3], [2, 3], [0, 0], [1, 2]]
- Ausgabe
- [18, 9, 2, 8]
- Erklärung
- Das gesamte Array ergibt
2 + 7 + 1 + 8 = 18, die letzten beiden Werte1 + 8 = 9, allein Index 02und die Indizes 1 bis 27 + 1 = 8.
+14 versteckte Tests beim Einreichen
Weiterführende Frage
Jetzt bilden die Zahlen ein Raster, und jede Abfrage fragt nach der Summe eines Rechtecks, das durch zwei Ecken definiert ist. Wie würdest du Präfixsummen erweitern, um jede Abfrage mit einer konstanten Anzahl von Operationen zu beantworten?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Viele Abfragen umfassen fast dieselben Werte. Welche Arbeit könntest du einmal erledigen, bevor du eine Abfrage liest?
Wenn du die Summe der ersten
iWerte für jedesikennen würdest, wäre ein Bereich die Differenz zwischen zwei dieser Summen.Erstelle
prefixmitprefix[0] = 0undprefix[i+1] = prefix[i] + nums[i]. Dann ist jede Abfrage[left, right]gleichprefix[right+1] - prefix[left].
Lösung
Ein Bereich entspricht einer Schleife. Das Problem ist ihre Anzahl: Jede Abfrage kann den größten Teil des Arrays umfassen, sodass jede einzeln zu addieren dieselben Additionen immer wieder wiederholt. Addiere alles einmal zu Präfixsummen auf, und jeder Bereich wird zu einer Subtraktion.
Addiere jeden Bereich
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Beantworte jede Anfrage einzeln: Setze eine Summe auf 0, addiere nums[left] bis nums[right] und speichere das Ergebnis. Für [1, 4] in [3, -2, 5, 1, -4, 6] ergibt das -2 + 5 + 1 + (-4) = 0.
Das ist korrekt und für eine einzelne Anfrage das Beste, was du tun kannst: Du musst jeden Wert im Bereich einmal lesen. Der Aufwand entsteht durch die Wiederholungen. Eine Anfrage kann bis zu n Werte umfassen, daher kosten q Anfragen bis zu n × q Additionen. Bei n = 10^4 und 1500 Anfragen, die jeweils den Großteil des Arrays abdecken, sind das etwa 1.3 × 10^7 Additionen, von denen fast alle Wiederholungen von Arbeit sind, die bereits für eine frühere Anfrage erledigt wurde.
Zusätzlich zur Ergebnisliste wird eine Summe gespeichert, daher beträgt der zusätzliche Speicherplatz O(1).
Algorithmus
- Erstelle eine leere Antwortliste.
- Setze für jede Abfrage
[left, right]total = 0. - Füge
nums[i]für jedesivonleftbisrighteinschließlich zutotalhinzu. - Füge
totalden Antworten hinzu und gib sie nach der letzten Abfrage zurück.
def sumRange(nums, queries):
answers = []
for left, right in queries:
total = 0
for i in range(left, right + 1):
total += nums[i]
answers.append(total)
return answersPräfixsummen
Idee
Sei prefix[i] die Summe der ersten i Werte, wobei prefix[0] = 0 für den leeren Anfang gilt. Für [3, -2, 5, 1, -4, 6] ergibt das prefix = [0, 3, 1, 6, 7, 3, 9]. Jeder Eintrag ist der vorherige plus einen Wert, daher benötigt das gesamte Array n Additionen.
Der Bereich [left, right] umfasst alles bis einschließlich Index right minus alles vor Index left. Das ist prefix[right+1] - prefix[left]. Für [1, 4]: prefix[5] - prefix[1] = 3 - 3 = 0. Für [0, 2]: prefix[3] - prefix[0] = 6 - 0 = 6. Die führende 0 sorgt dafür, dass ein Bereich, der bei Index 0 beginnt, ohne Sonderfall funktioniert.
Das Erstellen des Arrays kostet O(n), und jede Abfrage benötigt anschließend eine Subtraktion, sodass die Gesamtzeit O(n + q) und der zusätzliche Speicherbedarf O(n) beträgt. Keine Präfixsumme hier überschreitet den Wert 10^4 × 10^4 = 10^8, daher reichen 32-Bit-Ganzzahlen aus.
Algorithmus
- Erstelle
prefixder Längen+1mitprefix[0] = 0. - Setze für jedes
ivon0bisn-1prefix[i+1] = prefix[i] + nums[i]. - Füge für jede Abfrage
[left, right]prefix[right+1] - prefix[left]zu den Ergebnissen hinzu. - Gib die Ergebnisse zurück.
def sumRange(nums, queries):
# prefix[i] is the sum of the first i values, so prefix[0] = 0.
prefix = [0] * (len(nums) + 1)
for i, value in enumerate(nums):
prefix[i + 1] = prefix[i] + value
# nums[left..right] is the first right+1 values minus the first left values.
return [prefix[right + 1] - prefix[left] for left, right in queries]
Stolperfallen und Grenzfälle
Fast jeder Fehler hier ist ein Index, der um eins danebenliegt.
- Schreiben von
prefix[right] - prefix[left]. Mitprefix[0] = 0wird dadurchnums[right]ausgelassen, sodass der Bereich[3, 3]als0statt als Wert an Index 3 zurückgegeben wird. - Erstellen von
prefixmit derselben Länge wienums, sodassprefix[i]nums[i]einschließt. Dann benötigt ein bei0beginnender Bereichprefix[left-1], was außerhalb des gültigen Bereichs liegt und in Python stillschweigend den letzten Eintrag liest. Die zusätzliche führende0beseitigt diesen Sonderfall. - Beenden der Brute-Force-Schleife bei
i < right. Beide Enden des Bereichs sind eingeschlossen. - Vergessen, dass Lua und R bei 1 zu zählen beginnen. Die 0-basierte Abfrage
[left, right]umfasst dortnums[left+1]bisnums[right+1], und die Präfixdifferenz verschiebt sich genauso. - Verwenden einer 32-Bit-Summe, wenn die Werte oder Längen größer werden. Hier beträgt die größte Summe
10^8, aber bei Werten nahe10^9läuft eine Präfixsumme schnell über, und ein 64-Bit-Array ist die sichere Standardwahl.
Häufige Fragen4
Was ist ein Präfixsummen-Array?
Es ist ein Array, in dem jeder Eintrag die Summe aller Werte vor einer Position enthält: prefix[i] = nums[0] + ... + nums[i-1], wobei prefix[0] = 0 gilt. Du erstellst es in einem Durchlauf, und danach lässt sich die Summe jedes Bereichs [left, right] mit einer einzigen Subtraktion berechnen: prefix[right+1] - prefix[left].
Wie hoch ist die Zeitkomplexität von Bereichssummenabfragen mit Präfixsummen?
O(n), um das Präfixarray einmal aufzubauen, dann O(1) pro Abfrage, also O(n + q) für q Abfragen. Jeden Bereich direkt zu summieren, kostet bis zu O(n) pro Abfrage, also insgesamt O(n·q).
Warum hat das Präfix-Array einen Eintrag mehr als nums?
Das zusätzliche prefix[0] = 0 steht für den leeren Anfang des Arrays. Damit verwendet jeder Bereich dieselbe Formel, auch Bereiche, die bei Index 0 beginnen: prefix[right+1] - prefix[0]. Ohne dieses Element benötigst du einen eigenen Zweig für left = 0.
Was, wenn sich das Array zwischen Abfragen ändern kann?
Dann ist ein Präfixarray das falsche Werkzeug, weil eine Aktualisierung jede nachfolgende Summe verschiebt und es O(n) kostet, diese zu korrigieren. Ein Fenwick-Baum oder ein Segmentbaum verarbeitet sowohl eine Aktualisierung als auch eine Bereichssumme in O(log n). Wenn sich das Array nie ändert, sind einfache Präfixsummen schneller und kürzer.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def sumRange(nums, queries):
# Schreibe hier den CodeFall 1
Fall 2
Eingabe
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Erwartet
[6, 0, 1]