Jeden Bereich durch Subtraktion summieren

Das Erstellen des Präfixarrays war nur die Vorbereitung. Jetzt kommt der entscheidende Vorteil: Jede Bereichssumme lässt sich mit einer einzigen Subtraktion beantworten. ⚡

Eine Bereichssumme ist einfach eine große Gesamtsumme minus eine kleinere. Durch das Subtrahieren zweier Präfixwerte wird alles außerhalb Ihres Bereichs sauber herausgekürzt.

Um die Elemente von l bis r zu summieren, berechnen Sie prefix[r + 1] minus prefix[l]. Diese eine Formel funktioniert für jeden Bereich.

prefix[r + 1] enthält alles bis einschließlich r, und prefix[l] enthält alles vor l. Die Differenz lässt genau den mittleren Abschnitt übrig.

Für [3, 1, 4] lautet die Präfixsumme [0, 3, 4, 8]. Um die Indizes 1 bis 2 zu summieren, berechnen Sie 8 minus 3, also 5. Das entspricht 1 plus 4.

Jede Abfrage besteht nur aus einer Subtraktion und läuft daher in O(1). Tausend Abfragen kosten pro Abfrage genauso viel wie eine einzige.

Der häufigste Fehler betrifft den Index am oberen Ende. Mit einer führenden Null verwenden Sie immer prefix[r + 1], nicht prefix[r]. Achten Sie auf diese Grenze.

Entscheiden Sie früh, ob r enthalten ist. Diese Formel behandelt den Bereich als inklusiv für l und r, wie es die meisten Wettbewerbsaufgaben erwarten.

Eine kleine Hilfsfunktion hält Ihre Logik übersichtlich und Ihre Indizes an einer Stelle. Verwenden Sie diese Hilfsfunktion, statt die Berechnung direkt einzusetzen.

Um das gesamte Array zu summieren, verwenden Sie l gleich 0 und r gleich n minus 1. Die Formel liefert prefix[n], also die Gesamtsumme.

Immer wenn eine Aufgabe viele Bereichssummen für ein unverändertes Array abfragt, verwandeln Präfixsummen eine Schleife mit O(n) pro Abfrage in sofortige Antworten.

Sie möchten die Summe der Indizes von l bis r einschließlich berechnen.

Sie können jetzt jede Bereichssumme in O(1) mit prefix[r + 1] minus prefix[l] berechnen. Achten Sie auf den Versatz durch die führende Null, dann vermeiden Sie diesen Fehler. ✅