Summera valfritt intervall med subtraktion

Att bygga prefixarrayen var förberedelsen. Nu kommer det magiska: att besvara valfri intervallsumma med en enda subtraktion. ⚡

En intervallsumma är helt enkelt en stor totalsumma minus en mindre. Genom att subtrahera två prefixvärden tar du enkelt bort allt utanför intervallet.

För att summera elementen från l till r tar Ni prefix[r + 1] minus prefix[l]. Den här enda formeln fungerar för alla intervall.

prefix[r + 1] innehåller allt fram till och med r, medan prefix[l] innehåller allt före l. Skillnaden lämnar exakt mittsegmentet.

För [3, 1, 4] är prefix [0, 3, 4, 8]. För att summera index 1 till 2 tar Ni 8 minus 3, vilket ger 5. Det stämmer med 1 plus 4.

Varje fråga består bara av en subtraktion, så den körs på O(1). Tusen frågor kostar lika mycket per fråga som en enda.

Det vanligaste misstaget är indexet vid den övre gränsen. Med en inledande nolla använder Ni alltid prefix[r + 1], inte prefix[r]. Kontrollera den gränsen.

Avgör tidigt om r ska ingå. Den här formeln behandlar intervallet som inkluderande av både l och r, vilket de flesta tävlingsproblem förväntar sig.

En liten hjälpfunktion gör logiken lättläst och samlar indexhanteringen på ett ställe. Använd den här hjälpfunktionen i stället för att skriva ut matematiken direkt.

För att summera hela arrayen frågar Ni efter l lika med 0 och r lika med n minus 1. Formeln ger prefix[n], alltså totalsumman.

När ett problem ställer många frågor om intervallsummor i en oföränderlig array omvandlar prefixsummor en O(n)-loop per fråga till omedelbara svar.

Ni kan nu besvara alla intervallsummor i O(1) med prefix[r + 1] minus prefix[l]. Tänk på förskjutningen från den inledande nollan, så undviker Ni buggar. ✅