Prefix-summataulukon rakentaminen
Laske kertymät etukäteen kerran
Prefix-summataulukon rakentaminen on ilmainen Competitive Programming Academy-oppitunti CoddyKitissä. Tämä on oppitunti 1/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Toistuvien summien ongelma
Kuvittele vastaavasi satoihin yhden taulukon alueita koskeviin summakyselyihin. Jokaisen alueen summaaminen alusta lähtien on hidasta. Prefiksisumma ratkaisee ongelman. 🚀
Mikä prefiksisumma on
Prefiksisummataulukko tallentaa jokaiseen indeksiin kaikkien siihen asti olevien alkioiden summan. Yksi esilaskentakierros muuttaa hitaat summat välittömiksi vastauksiksi.
Pieni esimerkki
Taulukon [3, 1, 4] kumulatiiviset summat ovat 3, sitten 4 ja lopuksi 8. Tämä kasvava summien lista on juuri prefiksisumma.
Keskeinen palautuskaava
Jokainen alkio on edellinen summa plus nykyinen alkio. Tämä yksirivinen palautuskaava on koko tekniikan ydin.
prefix[i] = prefix[i - 1] + a[i]Rakenna se koodissa
Käy taulukko kerran läpi ja pidä mukana kumulatiivista summaa. Lisää uusi summa jokaisella askeleella, jolloin taulukon rakentaminen on yksi lineaarinen läpikäynti.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Miksi alussa oleva nolla auttaa
Kun prefiksisumma alkaa nollalla, prefix[i] sisältää ensimmäisen i:n alkion summan. Tämä tekee alueiden summien laskemisesta myöhemmin selkeää.
Indeksointisopimus
Kun alussa on nolla, prefix[k] on yhtä kuin a[0] + ... + a[k-1]. Tämän sopimuksen pitäminen mielessä estää tuskalliset yhden eron indeksivirheet.
Rakentamisen kustannus
Prefiksitaulukon rakentaminen käsittelee jokaisen alkion täsmälleen kerran, joten se vie aikaa O(n). Maksat tämän hinnan kerran ja voit käyttää taulukkoa sen jälkeen uudelleen.
Esilaske kerran, kysy usein
Suuri hyöty on tämä vaihtokauppa: käytä alussa yksi lineaarinen läpikäynti, jotta jokainen myöhempi summakysely muuttuu silmukan sijaan nopeaksi hauksi.
Python-tyylinen oikotie
Standardikirjasto voi muodostaa summat puolestasi. itertools.accumulate tuottaa kumulatiiviset summat yhdellä selkeällä kutsulla.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Tarkkaile muistia
Prefiksitaulukko on yhtä pitkä kuin syöte plus yksi alkio. Valtavilla syötteillä muista, että se kaksinkertaistaa muistijalanjälkesi.
Pikatarkistus
Rakennat prefiksitaulukkoa. Mitä indeksissä 0 yleensä on?
Kertaus
Opit rakentamaan prefiksisummataulukon yhdellä O(n)-läpikäynnillä ja lisäämään alkuun nollan selkeää indeksointia varten. Esilaske kerran ja käytä uudelleen. ✅
Opi Python tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Prefix-summataulukon rakentaminen” ilmainen?
Kyllä – oppitunnin ”Prefix-summataulukon rakentaminen” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Prefix-summataulukon rakentaminen”?
Laske kertymät etukäteen kerran Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 1/4.
Kuinka kauan ”Prefix-summataulukon rakentaminen”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Prefix-summataulukon rakentaminen
- Minkä tahansa välin summa vähentämällä
- Tavoitesumman sisältävien alitaulukoiden laskeminen
- Erotustaulukot välin päivityksiin