segmentträd

Segmentträd är en datastruktur som används för att effektivt hantera frågor om delintervall och uppdateringar i en sekvens av tal. Den gör det möjligt att svara på frågor som summa, min eller max över ett valt intervall och att uppdatera ett eller flera element i logaritmisk tid.

Strukturen består av ett binärt träd där varje nod motsvarar ett intervall [l, r] av den ursprungliga sekvensen. Rutorna (noderna) lagras ofta i en liknande struktur som en array. roten representerar hela intervallet, och varje inre nod delas i två halvor tills varje blad representerar ett enskilt element. Värdet i en nod beräknas som en sammanställning av dess barn enligt en associativ funktion (t.ex. summa, min, max).

Vanliga operationer är byggning (från en given sekvens), fråga om ett intervall och uppdatering av ett element. Byggning tar O(n) tid. Frågor och punktuppdateringar tar O(log n) tid. För stöd för uppdateringar över hela intervall används lazy-propagation, vilket gör att konsekvent uppdatering av intervall kan ske i O(log n) per operation, utan att uppdatera varje enskild nod omedelbart.

Minne krävs O(n) plats, ofta ungefär fyra n i storlek i en arraybaserad implementation. Segmentträdet är särskilt användbart när operatören är anpassningsbar och inte begränsar sig till prefix- eller suffixfunktioner, såsom sum, min, max, gcd eller antal förekomster inom ett intervall. Jämfört med Fenwick-trädet är segmentträdet mer flexibelt för olika operationer, men kan vara mindre minnes- och kod-effektivt för enkla fall.