Segmenttre: bygg og spør
Finn minimum, maksimum eller sum i et intervall på log n-tid
Segmenttre: bygg og spør er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 3 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.
Videre enn Fenwick-treet
Et Fenwick-tre er utmerket for summer, men et segmenttre håndterer minimum, maksimum, gcd og mer. Det er det fleksible arbeidstreet for intervallspørringer.
Et tre over intervaller
Hver node eier et intervall i arrayet. Roten dekker alt, og barna deler intervallet i to helt til bladene inneholder enkeltelementer.
Array-basert lagring
Vi lagrer treet i et flatt array med størrelse 2n eller 4n. Node 1 er roten; barna til node i ligger på 2i og 2i+1.
seg = [0] * (2 * n)Bladene inneholder dataene
I den iterative formen ligger de opprinnelige verdiene i andre halvdel av arrayet, på indeksene n til 2n-1.
for i in range(n):
seg[n + i] = a[i]Bygg nedenfra og opp
Hver intern node er combine av de to barna sine. Fyll dem ut fra n-1 og ned til 1, så er hele treet klart.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]Kombinasjonsoperasjonen
combine-funksjonen definerer treet. Bruk pluss for summer, min for minimum eller max for maksimum. Bytt den ut for å endre spørringen.
def combine(x, y):
return min(x, y)Punktoppdatering, så klatrer du opp
For å endre én verdi setter du bladet og går opp til roten, mens du beregner på nytt hver forelder ut fra de to barna underveis.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Spørr i et halvåpent intervall
Intervallspørringer skanner fra begge ender og kombinerer grensenoder i svaret. Intervallet er halvåpent og dekker l opp til, men ikke med, r.
Den iterative spørringsløkken
Flytt l og r mot hverandre. Når en indeks er en odde grense, tar du med den noden før du flytter pekeren.
while l < r:
if l & 1: res = combine(res, seg[l]); l += 1
if r & 1: r -= 1; res = combine(res, seg[r])
l //= 2; r //= 2Logaritmisk i begge ender
Bygging er O(n), mens hver oppdatering og spørring er O(log n). Det er denne balansen som gjør segmenttrær så allsidige.
Husk identitetselementet
Start resultatet med operasjonens identitetselement: 0 for sum, uendelig for min og minus uendelig for max. En feil startverdi gir feil svar.
res = float('inf')Rask sjekk
Hvor ligger rådataene i det iterative treet?
Oppsummering: Fleksible intervaller
Du bygde et segmenttre: blader i andre halvdel, foreldre som kombinasjoner, med O(log n)-oppdateringer og -spørringer for sum, min eller max. 🌳
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 «Segmenttre: bygg og spør» gratis?
Ja – hele teksten i «Segmenttre: bygg og spør» 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 «Segmenttre: bygg og spør»?
Finn minimum, maksimum eller sum i et intervall på log n-tid 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 3 av 4.
Hvor lang tid tar leksjonen «Segmenttre: bygg og spør»?
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
- Fenwick-tre for prefikssummer
- Inversjoner med en BIT
- Segmenttre: bygg og spør
- Lat oppdatering for intervalloppdateringer