Een prefixsomarray bouwen

Stel je voor dat je honderden vragen over sommen van bereiken op één array moet beantwoorden. Elk bereik vanaf nul optellen is traag. Een prefixsom lost dat op. 🚀

Een array met prefixsommen bewaart op elke index het totaal van alle elementen tot en met die positie. Eén voorbereidende doorgang verandert trage sommen in directe antwoorden.

Voor [3, 1, 4] zijn de oplopende totalen 3, daarna 4 en daarna 8. Die groeiende lijst met totalen is precies je prefixsom.

Elke waarde is het vorige totaal plus het huidige element. Deze eenregelige recursie vormt de kern van de hele techniek.

Doorloop de array één keer en houd een oplopend totaal bij. Voeg bij elke stap de nieuwe som toe, zodat het opbouwen van de array één enkele lineaire doorgang is.

Als je prefix met een voorloop-nul begint, bevat prefix[i] de som van de eerste i elementen. Daardoor wordt rekenen met bereiken later eenvoudig.

Met de nul vooraan is prefix[k] gelijk aan a[0] + ... + a[k-1]. Als je deze conventie goed toepast, voorkom je pijnlijke fouten waarbij je één positie te ver zit.

Bij het opbouwen van de prefixarray raak je elk element precies één keer aan, dus het kost O(n)-tijd. Je betaalt die kosten één keer en gebruikt het resultaat daarna steeds opnieuw.

De grote winst is de afweging: besteed vooraf één lineaire doorgang, zodat elke latere somvraag een snelle opzoekactie wordt in plaats van een lus.

De standaardbibliotheek kan de totalen voor je opbouwen. itertools.accumulate levert de oplopende sommen in één overzichtelijke aanroep.

De prefixarray heeft dezelfde lengte als je invoer plus één. Houd er bij enorme invoer rekening mee dat dit je geheugengebruik verdubbelt.

Je hebt geleerd hoe je in één doorgang van O(n) een array met prefixsommen opbouwt, met een voorloopnul voor eenvoudige indexering. Bereken het één keer vooraf en gebruik het daarna opnieuw. ✅