Segment Tree: bouwen en query's uitvoeren
Minimum, maximum of som van een bereik in log n
Segment Tree: bouwen en query's uitvoeren is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 3 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Verder dan de Fenwick-boom
Een Fenwick-boom blinkt uit in sommen, maar een segmentboom ondersteunt minimum, maximum, ggd en meer. Het is het flexibele werkpaard voor bereiksvragen.
Een boom over bereiken
Elke knoop beheert een bereik van de array. De wortel bestrijkt alles; kinderen splitsen het bereik in tweeën totdat bladeren afzonderlijke elementen bevatten.
Opslag in een array
We slaan de boom op in een platte array met grootte 2n of 4n. Knoop 1 is de wortel; de kinderen van knoop i staan op 2i en 2i+1.
seg = [0] * (2 * n)Bladeren bevatten de gegevens
In de iteratieve vorm staan de oorspronkelijke waarden in de tweede helft van de array, op indexen n tot en met 2n-1.
for i in range(n):
seg[n + i] = a[i]Van onder naar boven opbouwen
Elke interne knoop is de combinatie van zijn twee kinderen. Vul ze in van n-1 naar 1 en de hele boom is klaar.
for i in range(n - 1, 0, -1):
seg[i] = seg[2*i] + seg[2*i+1]De combinatiebewerking
De functie combine bepaalt de boom. Gebruik plus voor sommen, min voor minimumwaarden of max voor maximumwaarden. Vervang deze functie om de vraag te veranderen.
def combine(x, y):
return min(x, y)Positie bijwerken en omhoog gaan
Om één waarde te veranderen, stel je het blad in en loop je naar de wortel. Onderweg bereken je elke ouder opnieuw op basis van zijn twee kinderen.
i += n
seg[i] = value
while i > 1:
i //= 2
seg[i] = combine(seg[2*i], seg[2*i+1])Een halfopen bereik opvragen
Bereiksvragen lopen vanaf beide uiteinden en voegen grensknopen samen in het antwoord. Het interval is halfopen en omvat l tot maar niet r.
De iteratieve vraaglus
Beweeg l en r naar elkaar toe. Wanneer een index een oneven grens vormt, neem je die knoop op voordat je de aanwijzer verplaatst.
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 //= 2Logaritmisch aan beide kanten
De opbouw kost O(n), terwijl elke update en vraag O(log n) kost. Die balans maakt segmentbomen zo veelzijdig.
Let op het neutrale element
Begin je resultaat met het neutrale element van de bewerking: 0 voor een som, oneindig voor een minimum en min oneindig voor een maximum. Met het verkeerde begin krijg je verkeerde antwoorden.
res = float('inf')Korte controle
Waar staan de onbewerkte gegevens in de iteratieve boom?
Samenvatting: flexibele bereiken
Je hebt een segmentboom gebouwd: bladeren in de tweede helft, ouders als combinaties, met updates en vragen in O(log n) voor som, minimum of maximum. 🌳
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Segment Tree: bouwen en query's uitvoeren” gratis?
Ja — de volledige tekst van “Segment Tree: bouwen en query's uitvoeren” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Segment Tree: bouwen en query's uitvoeren”?
Minimum, maximum of som van een bereik in log n Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 3 van 4.
Hoe lang duurt de les “Segment Tree: bouwen en query's uitvoeren”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Fenwick Tree voor prefixsommen
- Inversies met een BIT
- Segment Tree: bouwen en query's uitvoeren
- Lazy propagation voor bereikupdates