Bygg et prefikssumarray
Forhåndsberegn løpende totaler én gang
Bygg et prefikssumarray er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Problemet med gjentatte summer
Tenk deg at du skal svare på hundrevis av spørsmål om intervallsummer i ett array. Å summere hvert intervall fra grunnen av er tregt. En prefikssum løser dette. 🚀
Hva en prefikssum er
Et array med prefikssummer lagrer totalsummen av alle elementene frem til hvert enkelt indeks. Én forhåndsberegning gjør langsomme summeringer om til umiddelbare svar.
Et lite eksempel
For [3, 1, 4] er de løpende summene først 3, så 4 og deretter 8. Denne voksende listen med summer er nettopp prefikssummen.
Den grunnleggende rekurrensen
Hver oppføring er den forrige totalsummen pluss det gjeldende elementet. Denne enlinjers rekurrensen er kjernen i hele teknikken.
prefix[i] = prefix[i - 1] + a[i]Implementer det i kode
Gå gjennom arrayet én gang mens du holder rede på en løpende sum. På hvert trinn legger du den nye summen til, så byggingen av arrayet blir én lineær gjennomgang.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Hvorfor en innledende null hjelper
Hvis du starter prefix med en innledende null, inneholder prefix[i] summen av de første i elementene. Det gjør intervallberegninger enklere senere.
Indekseringskonvensjonen
Med null først er prefix[k] lik a[0] + ... + a[k-1]. Hvis du holder denne konvensjonen fast, unngår du smertefulle feil med én forskyvning.
Kostnaden ved å bygge arrayet
Byggingen av prefiksarrayet går gjennom hvert element nøyaktig én gang, så den koster O(n) tid. Du betaler denne kostnaden én gang og kan deretter bruke resultatet på nytt.
Forhåndsberegn én gang, bruk ofte
Den store gevinsten er avveiningen: Bruk én lineær gjennomgang på forhånd, slik at hvert senere spørsmål om en sum blir et raskt oppslag i stedet for en løkke.
En Python-idiomatisk snarvei
Standardbiblioteket kan bygge summene for deg. itertools.accumulate produserer de løpende summene i ett ryddig kall.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Pass på minnet
Prefiksarrayet er like langt som inndataene dine pluss én. For svært store inndata må du huske at det dobler minnebruken.
Kort kontroll
Du bygger et prefiksarray. Hva inneholder indeks 0 vanligvis?
Oppsummering
Du har lært å bygge et array med prefikssummer i én gjennomgang på O(n), med en innledende null for enkel indeksering. Forhåndsberegn én gang, og bruk resultatet på nytt. ✅
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Bygg et prefikssumarray» gratis?
Ja – hele teksten i «Bygg et prefikssumarray» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Bygg et prefikssumarray»?
Forhåndsberegn løpende totaler én gang Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Bygg et prefikssumarray»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Bygg et prefikssumarray
- Summer et vilkårlig intervall med subtraksjon
- Tell subarrayer med en målsum
- Differansearrayer for intervalloppdateringer