Segmentbomen

Segmentbomen zijn een datastructuur die is ontworpen om snelle queries en updates over opeenvolgende intervallen mogelijk te maken. Ze worden opgebouwd over een array van n elementen en elke knoop van de boom komt overeen met een interval [l, r]. In elk knooppunt wordt een samenvatting opgeslagen van de elementen binnen dat interval, bijvoorbeeld de som, de minimale of maximale waarde, of een andere associatieve bewerking. Segmentbomen maken efficiënte range queries en point updates mogelijk.

De boom wordt meestal als een volledige binaire boom geïmplementeerd, waarbij de bladeren de elementen van de array representeren en ouderknooppunten de samenvoeging van hun kinderen beschrijven. Bouwtijd is O(n) voor een juiste implementatie, en een query of update kost doorgaans O(log n) tijd, wat leidt tot snelle verwerkingen bij meerdere bewerkingen.

Typische bewerkingen zijn: het berekenen van een beoogde bewerking over een interval [L, R] (bijv. som, min of max), en het bijwerken van een enkel element. Voor range-updates die opeenvolgende elementen tegelijk veranderen, wordt vaak lazy propagation gebruikt om onnodige herberekeningen uit te stellen en de tijdcomplexiteit te behouden.

Segmentbomen kunnen verschillende associatieve bewerkingen ondersteunen door de samenvoegingsfunctie aan te passen. Ze vereisen doorgaans geheugenruimte van ongeveer 4n elementen. In de praktijk worden ze vaak vergeleken met Fenwick-bomen (BIT), hoewel segmentbomen meer flexibiliteit bieden qua operaties en range-updates.

Toepassingen van segmentbomen zijn wijdverspreid in computerwetenschap en programmeren, vooral bij problemen met range-queries en dynamische datasets. Ze worden veel gebruikt in competitieprogrammeren vanwege hun logaritmische bewerkingstijd en de flexibiliteit om verschillende samenvattende bewerkingen te combineren.