Range Sum Query
Du erhältst ein Array aus ganzen Zahlen nums, das sich nie ändert, und eine Liste von queries. Jede Abfrage ist ein Paar [left, right] aus 0-basierten Indizes und fragt nach nums[left] + nums[left+1] + ... + nums[right], wobei beide Endpunkte 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]enthält den einzelnen 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
18, die letzten beiden Werte1 + 8 = 9, allein Index 02und die Indizes 1 bis 27 + 1 = 8.
Weiterführende Frage
Wenn die Zahlen ein Raster bilden und jede Abfrage nach der Summe eines Rechtecks fragt, wie würdest du Präfixsummen erweitern, um jede Abfrage in konstanter Zeit zu beantworten?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Viele Abfragen decken fast dieselben Werte ab. 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 einzelner Bereich ist eine Schleife, aber jede Abfrage kann den größten Teil des Arrays umfassen, sodass das separate Summieren jedes Bereichs dieselben Additionen wiederholt. Addiere das Array einmal zu Präfixsummen auf, und jeder Bereich wird zu einer einzigen Subtraktion.
Addiere jeden Bereich
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Addiere für jede Abfrage nums[left] bis nums[right] zu einer Summe. Das ist korrekt, weil dabei jeder Wert im Bereich gelesen wird, und für eine Abfrage ist das die beste Vorgehensweise. Eine Abfrage kann bis zu n Werte umfassen, daher erfordern q Abfragen bis zu n × q Additionen: 1.5 × 10^7, wenn n = 10^4 und q = 1500, wobei sich fast alle wiederholen.
Algorithmus
- Erstelle eine leere Antwortliste.
- Setze für jede Abfrage
[left, right]total = 0. - Addiere
nums[i]für jedesivonleftbisright, einschließlich beider Grenzen, zutotal. - 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 [3, -2, 5, 1, -4, 6] ergibt das [0, 3, 1, 6, 7, 3, 9].
Der Bereich [left, right] umfasst alles bis zum Index right abzüglich allem vor dem Index left: prefix[right+1] - prefix[left]. Für [1, 4] ist das prefix[5] - prefix[1] = 3 - 3 = 0. Die führende 0 ermöglicht es, für einen Bereich, der bei Index 0 beginnt, dieselbe Formel zu verwenden. Ein Durchlauf mit n Additionen erstellt das Array, und jede Abfrage erfordert dann nur eine Subtraktion.
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 Antworten hinzu. - Gib die Antworten 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
prefix[right] - prefix[left]schreiben. Mitprefix[0] = 0wird dadurchnums[right]ausgelassen, sodass der Bereich[3, 3]0statt1ergibt.prefixso lang wienumsmachen, sodassprefix[i]nums[i]enthält. Ein Bereich, der bei 0 beginnt, benötigt dannprefix[-1], was außerhalb des gültigen Bereichs liegt, und Python liest stattdessen stillschweigend den letzten Eintrag.- Die Brute-Force-Schleife bei
i < rightbeenden. Beide Endpunkte sind eingeschlossen, daher würde[3, 3]nichts summieren. - In Lua und R, die bei 1 zu zählen beginnen, umfasst die 0-basierte Abfrage
[left, right]die Elemente vonnums[left+1]bisnums[right+1], und die Präfixindizes verschieben sich genauso.
Häufige Fragen3
Was ist ein Präfixsummenarray?
Ein Array, in dem jeder Eintrag die Summe aller Werte vor einer Position ist: prefix[i] = nums[0] + ... + nums[i-1], wobei prefix[0] = 0 gilt. Du erstellst es in einem Durchlauf. Anschließend ist die Summe eines beliebigen Bereichs [left, right] gleich 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 aufzusummieren kostet bis zu O(n) pro Abfrage, insgesamt O(n·q).
Was ist, wenn sich das Array zwischen den Abfragen ändern kann?
Dann ist ein Präfixarray das falsche Werkzeug, denn jede Aktualisierung verschiebt alle darauf folgenden Summen und kostet O(n), um sie zu korrigieren. Ein Fenwick-Baum oder ein Segmentbaum verarbeitet sowohl eine Aktualisierung als auch eine Bereichssumme in O(log n).
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def sumRange(nums, queries):
# Schreibe hier CodeTest #1
Test #2
Argumente
nums = [3, -2, 5, 1, -4, 6] queries = [[0, 2], [1, 4], [3, 3]]
Erwartete Ausgabe
[6, 0, 1]