Segmentträdet

Segmentträdet, eller segment tree, är en datastruktur som används för att effektivt hantera intervallfrågor och uppdateringar i en array. Varje nod i trädet motsvarar ett segment av originalarrayen, och lövet representerar ett enskilt element. Värdet i varje intern nod är resultatet av en associativ operation över elementen i dess segment, till exempel summa, minimum eller maximum. Trädet byggs rekursivt genom att dela intervallet tills varje segment består av ett enda element, och sedan sätts noderna som operationen av deras barn.

Byggnad och minne: Byggnaden av trädet tar vanligtvis O(n) tid. Minnesbehovet är vanligtvis upp till cirka fyra noder per element, så ungefär O(n).

Operationer: En intervallfråga (range query) körs i O(log n) tid, och en uppdatering av ett enskilt element i O(log n). För intervalluppdateringar kan lazy propagation användas, vilket gör att uppdateringar över ett helt intervall ofta hanteras i O(log n) tid per uppdatering utan att varje element uppdateras direkt.

Varianter och användningsområden: Den vanligaste varianten är lazy segment tree, som stödjer både intervallfrågor och intervalluppdateringar. Persistenta segmentträd används när man vill bevara tidigare versioner av arrayen. Segmentträdet är flexibel och kan användas för olika funktioner som sum, min, max och gcd, vilket gör det användbart i tidsserieanalys, dynamiska databassammanställningar och andra applikationer där snabba intervalloperationer behövs.

Jämförelse: Till skillnad från Fenwick-trädet är segmentträdet mer flexibelt när operationen på intervallet inte är invertibel eller när olika typer av intervallfunktioner används. Fenwick är ofta enklare och snabbare för rena prefixsummor.