Lõikude puu

Lõikude puu on struktuurilt kuhjaga sarnane tasakaalustatud kahendpuu kujuline andmestruktuur, mis salvestab mingit infot lõikude kohta. Selle struktuur on staatiline: seda ei saa peale konstrueerimist muuta. Tihti ehitatakse lõikude puu mingi arvujada peale, kus infot hoitakse selle jada elementide vahemike kohta.

Lõikude puu kasutab  mälu ja selle saab konstrueerida  ajaga. Lõikude puuga saab lahendada vahemikust miinimumi pärimise (ingl Range Minimum Query, RMQ) probleemi  ajaga.S. Halim, F.Halim (2013). Competitive Programming 3 The New Lower Bound of Programming Contests, lk 55.

Struktuur

Lõikude puul vastab iga tipu lõik oma alamate lõikude ühendile. Üldiselt vastavad lehtede lõigud mingi suurema terviklõigu tükeldusele, ehk lehtede lõigud on ühisosadeta ja järjestatud vasakult paremale. Tulemusena on igal sügavusel olevate tippude lõigud paarikaupa ühisosata ja lisaks on iga tipu enda vahemik tükeldamata tervik. Just need omadused teevad lõikude puust pärimise kiireks. 

Operatsioonid

Lõikude puul saab  ajaga käsitleda aluseks olevas jadas üksiku elemendi väärtuse muutumist. Sellisel juhul tuleb lihtsalt uuendada vastav leht ja kõik tipud, mis jäävad teele sellest lehest puu juureni.

Kui lõikude puu tipud salvestavad vastava lõigu miinimumi, siis on võimalik pärida  ajaga suvalise alusjada vahemiku miinimumi järgneva rekursiivse algoritmi abil:
 Kui tipu vahemik on päritud vahemiku sees, siis väljasta tipu miinimum
 Kui vasak alamtipp omab ühisosa päritava lõiguga, siis tee rekursiivne päring sellelt alamtipult
 Kui parem alamtipp omab ühisosa päritava lõiguga, siis tee rekursiivne päring sellelt alamtipult
 Väljasta rekursiivsetelt päringutelt saadud vastuste miinimum

Algoritm omab ülalmainitud ajalist keerukust, kuna igal sügavusel on ülimalt kaks tippu, millest tehakse rekursiivne kutse. See kehtib, kuna peale esimest hargnemist on igal sügavamal päringul kas üks tipp täielikult päritava vahemiku sees või teine täielikult sellest väljas.Data Structures Programmeerimisvõistlused 2017 Kasutatud 26.04.2018

Täiendused

Lõikude puule eksisteerib täiendusi, mis võimaldavad selle abil rohkem probleeme lahendada. Mõned näited:

Laisa laienemise meetod

Laisk laienemine (ingl Lazy Propagation) on lähenemine, kus lõigu uuendamise päringutel lükatakse tippude uuendamise edasi hetkeni, kus nende andmeid reaalselt vaja läheb. Meetodi töötamiseks peavad lõigu uuendamise päringud olema korrapärased, näiteks kõigile sama uue väärtuse andmine või kõigi suurendamine mingi sama konstandi võrra. Sisuliselt tehakse võimalikult kõrgetele tippudele märgistus et nendel tuleb see uuendus teha. Tulevikus kui tipu väärtust vaja läheb rakendatakse tipule märgistatud uuendus ja saadetakse märgistus tipu alamatele edasi. See võimaldab lõikude uuendamist teha  ajaga.Data Structures, Advanced Concepts Programmeerimisvõistlused 2017 Kasutatud 26.04.2018A Recursive approach to Segment Trees, range sum queries & lazy propagation LeetCode Kasutatud 26.04.2018

Püsiv lõikude puu

Püsiv lõikude puu (ingl Persistent Segment Tree) on lõikude puu variant, mis võimaldab teha ajaloolisi päringuid, näiteks mis oli mineviku ajahetkel t mingi lõigu elementide miinimum. Tasub tähele panna, et mingi üksiku lehe väärtuse uuenemisel tuleb lõikude puus uuendada ainult  lehti. Püsiv lõikude puu loob peale iga uuendust uue versiooni lõikude puust, aga iga versioon lisab ainult  tippu, mis vastavad uuendatud teele jäävatele tippudele. Uue tipu mitteuuendatud alamatipp asub mingis varasemas versioonis, ehk uuema versiooni tipud võivad omada varasemate versioonide tippe alamatena. See trikk võimaldab  aja ja mälu kuluga uuendamist ja  ajaga ajaloolist päringut.

Viited

Kategooria:Informaatika