Segmenttræ: opbygning og forespørgsler
Interval-min, -max eller -sum i log n
Segmenttræ: opbygning og forespørgsler er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Ud over Fenwick-træet
Et Fenwick-træ er fremragende til summer, men et segmenttræ håndterer min, max, gcd og meget mere. Det er den fleksible arbejdshest til intervalforespørgsler.
Et træ over intervaller
Hver knude dækker et interval i arrayet. Roden dækker alt, og børnene deler intervallet i to, indtil bladene indeholder enkelte værdier.
Arraybaseret lager
Vi gemmer træet i et fladt array med størrelsen 2n eller 4n. Knude 1 er roden, og børnene til knude i ligger ved 2i og 2i+1.
seg = [0] * (2 * n)Bladene indeholder dataene
I den iterative form ligger de oprindelige værdier i anden halvdel af arrayet ved indeks n til 2n-1.
for i in range(n):
seg[n + i] = a[i]Byg nedefra og op
Hver intern knude er combine af sine to børn. Udfyld dem fra n-1 ned til 1, så er hele træet klar.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]Kombinationsoperationen
Funktionen combine definerer træet. Brug plus til summer, min til minimumsværdier eller max til maksimumsværdier. Skift den ud for at ændre forespørgslen.
def combine(x, y):
return min(x, y)Punktopdatering, derefter opad
Hvis du vil ændre én værdi, skal du sætte bladet og gå op til roden, mens du genberegner hver forælder ud fra dens to børn.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Forespørg i et halvlukket interval
Intervalforespørgsler gennemgår området fra begge ender og kombinerer grænseknuder i svaret. Intervallet er halvlukket og dækker l op til, men ikke inklusive, r.
Den iterative forespørgselsløkke
Flyt l og r mod hinanden. Når et indeks er en ulige grænse, skal du tage den knude med, før du flytter markøren.
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
Opbygningen er O(n), mens hver opdatering og forespørgsel er O(log n). Det er denne balance, der gør segmenttræer så alsidige.
Husk identitetselementet
Start resultatet med operationens identitetselement: 0 for sum, uendelighed for min og negativ uendelighed for max. En forkert startværdi giver forkerte svar.
res = float('inf')Hurtigt tjek
Hvor ligger rådataene i det iterative træ?
Opsummering: Fleksible intervaller
Du byggede et segmenttræ: Blade i anden halvdel, forældre som kombinationer og O(log n)-opdateringer og -forespørgsler for sum, min eller max. 🌳
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Segmenttræ: opbygning og forespørgsler” gratis?
Ja — hele teksten til “Segmenttræ: opbygning og forespørgsler” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Segmenttræ: opbygning og forespørgsler”?
Interval-min, -max eller -sum i log n Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Segmenttræ: opbygning og forespørgsler”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Fenwick-træ til præfikssummer
- Inversioner med en BIT
- Segmenttræ: opbygning og forespørgsler
- Lazy propagation til intervalopdateringer